Let $n$ be positive integer such that there are exactly 36 different prime numbers that divides $n.$ For $k=1,2,3,4,5,$ $c_n$ be the number of integers that are mutually prime numbers to $n$ in the interval $[\frac{(k-1)n}{5},\frac{kn}{5}] .$ $c_1,c_2,c_3,c_4,c_5$ is not exactly the same.Prove that$$\sum_{1\le i<j\le 5}(c_i-c_j)^2\geq 2^{36}.$$
Problem
Source: Changsha
Tags: number theory, inequalities, algebra, China, Bashing
26.11.2020 15:02
Fixed @below. Let $n=\prod p_i^{\alpha_i}$. Let $d_1(x)$ denote the number of multiples of $x$ in the first interval, and define $d_2(x), \cdots ,d_5(x)$ likewise. Note that by PIE, we have $$c_1 = d_1(1) - \sum_i d_1(p_i) + \sum_{i,j} d_1(p_ip_j) - \cdots +d_1(\prod p_i)$$Likewise, we have a similar expression for $c_2, \cdots ,c_5$. Let $e_1(x)$ be the number of fractions of the form $\frac m x$, $m\in \mathbb Z$ that are in the interval $[0,\frac 1 5]$, and define $e_2(x), \cdots e_5(x)$ similarly. It is not hard to see that if $x \mid n$, then $d_i(x) = e_i(\frac n x)$. Letting $m = \frac n {\prod p_i}$, we get \begin{align} c_1 = e_1(m) - \sum_i e_1(mp_i) + \sum_{i,j} e_1(mp_ip_j) - \cdots +e_1(m\prod p_i) \end{align} To sum this, we need to observe how $e_i(x)$ behaves. If $x \equiv 0 \pmod 5$, it is clear that $e_1=e_2=e_3=e_4=e_5$. We can just subtract the same number from everything and the required sum of squares stays the same, so we take $(e_1,e_2,e_3,e_4,e_5)= (0,0,0,0,0)$ If $x \equiv 1 \pmod 5$, we know that $\sum e_i \equiv 2 \pmod 5$. Also, we know that $e_i \in \{ \lfloor \frac{x+2}{5} \rfloor , \lceil \frac{x+2}{5} \rceil \}$. It is clear that $e_1=e_5 = \lceil \frac{x+2}{5} \rceil $ (because they contain a term at one end of the interval), so we must have $e_2=e_3=e_4 = \lfloor \frac{x+2}{5} \rfloor$. Hence, $(e_1,e_2,e_3,e_4,e_5) = (k+1, k, k, k, k+1)$ which we can treat as $(1,0,0,0,1)$. If $x \equiv 2 \pmod 5$, we have $\sum e_i \equiv 3 \pmod 5$, with $e_1=e_5 = \lceil \frac{x+3}{5} \rceil $.From symmetry, we know that $e_2=e_4$, so we must have $e_3 = \lceil \frac{x+3}{5} \rceil$, $e_2=e_4=\lfloor \frac{x+2}{5} \rfloor$. We take $(e_1,e_2,e_3,e_4,e_5) = (1,0,1,0,1)$. For $x \equiv 3 \pmod 5$, $(e_1,e_2,e_3,e_4,e_5) = (1,1,0,1,1)$, and lastly, for $x \equiv 4 \pmod 5$, $(e_1,e_2,e_3,e_4,e_5) = (1,1,1,1,1)$ (all equal). Consider when $n$ is a multiple of $5$. Then if $m$ is also a multiple of $5$, all $e_i$ are $0$, so all $c_i$ are $0$ and thus were initially equal, a contradiction. If $m$ is not a multiple of $5$, then WLOG $p_1=5$. Every $e_1(x)$ term in (1) where $p_1 \mid x$ will evaluate to $0$, and likewise for $e_2(x), \cdots , e_5(x)$. Hence, the sum in (1) reduces to the case where we have essentially 35 primes, where $n$ is no longer a multiple of $5$. Now, we have two cases: $n$ is not a multiple of $5$, and there are $35$ or $36$ primes. We deal with the $35$ case as it is tighter (repeat the same for $36$). Note that since $e_1$ and $e_5$ are always $1$, we have $$c_1 = e_1(m) - \sum_i e_1(mp_i) + \sum_{i,j} e_1(mp_ip_j) - \cdots +e_1(m\prod p_i) = (1-1)^{35} = 0 $$likewise, $c_5=0$. For $c_2$, we want to make the PIE sum nice by making $e_2(x)$ multiplicative. Note that $2$ is a generator of $\mathbb F_5^{\times}$. We have $e_2(2)=0, e_2(2^2)=1, e_2(2^3)=1, e_2(2^4)=0$. We can calculate that $e_2(2^x)=\frac 1 4 (2+(-1-i)i^x+(i-1)i^{3x})$ by inverse discrete fourier transform. Then, we let $x_i$ be such that $p_i \equiv 2^{x_i} \pmod 5 $, and $m\equiv 2^x \pmod 5$. $$c_2 =e_2(2^x) - \sum_i e_2(2^{x+x_i}) + \sum_{i,j} e_2(2^{x+x_i+x_j}) - \cdots $$$$= \frac 1 4 (2\prod_j(1-1)+(-1-i)i^x\prod_j (1-i^{x_j})+(-1+i)i^{3x}\prod_j (1-i^{3x_j})) $$ We see that the first term in the sum evaluates to $0$. Letting, $a=(-1-i)i^x\prod_{j=1}^{35} (1-i^{x_j})$, we have $c_2 = c_4 = \frac 1 4 (a+\overline{a})$. We repeat for $c_3$. We have $e_3(2)=1, e_3(2^2)=1, e_3(2^3)=0, e_3(2^4)=0$, so $e_3(2^x)=\frac 1 4 (2+(1-i)i^x+(1+i)i^{3x})$. We get $$c_3 = \frac 1 4 (2+(1-i)i^x\prod_j (1-i^{x_j})+(1+i)i^{3x}\prod_j (1-i^{3x_j})) = \frac 1 4 (ia - i\overline{a})$$ Now, $S=\sum_{i<j} (c_i-c_j)^2 = 4(\sum_i c_i^2) - 2\sum_{i<j}c_ic_j = 6c_2^2 + 4c_3^2 - 4c_2c_3 = \frac {1}{16} ((2-4i)a^2 + (2+4i)\overline{a}^2 + 20a\overline{a}$, simplifying to $$S= \frac {1}{8} ((1-2i)a^2 + (1+2i)\overline{a}^2 + 10a\overline{a})$$Note that we have $(1+i)^{36} \mid a$. We divide into cases: If $(1+i)^{39} \mid a$, then $\frac{(1+i)^{78}}{8} \mid S$, since $S$ is an integer, $2^{36}\mid S$. Otherwise, we have 3 cases: Case 1: $(1+i)^{36} \mid \mid a$. Since $a$ only has prime factors (in gaussian integers) of the form $(1+i)$, we know that $a=\pm 2^{18}, \pm i2^{18}$. Substituting all values in, we can check that $S\ge 2^{36}$. Case 2: $(1+i)^{37} \mid \mid a$. Then $a = 2^{18}(\pm 1 \pm i)$. Again, we substitute to check that $S\ge 2^{36}$. Case 3: $(1+i)^{38} \mid \mid a$. Same as case 1, but looser.
26.11.2020 15:46
Can someone check if @above's solution is correct? I tried with 6 primes and n=5*2*3*13*23*43=385710, then the sum is exactly 64
26.11.2020 16:08
Justanaccount wrote: Can someone check if @above's solution is correct? I tryed with $6$ primes and $n=5 \cdot 2 \cdot 3 \cdot 13 \cdot 23 \cdot 43=385710$, then the $\sum$ is exactly $64$ FTFY
26.11.2020 18:39
I am not sure I understand the problem correctly: Is the assumption that the $c_i$ are not all the same, or that they are (pairwise) distinct?
26.11.2020 18:44
They are not all the same, you can easily see that c5=c1,c4=c2
05.12.2020 07:45
First of all, one could easy see that if $25|n$ then $c_1=c_2=c_3=c_3=c_4=c_5$ so we assume the converse. Also it is evident that $c_5=c_1, c_4=c_2$. Further, there exist exactly $$\sum_{d|n} \mu(d) \left [\frac{an}{5d}\right ] = \sum_{d|n} \mu(d) \frac{an}{5d} - \sum_{d|n} \mu(d) \left \{\frac{an}{5d}\right \}$$numbers that are coprime to $n$ and less than $an/5$, so the next equalities are true $$c_2-c_1=(c_1+c_2)-2c_1=\sum_{d|n}\mu(d) \left (2\left \{\frac{n}{5d}\right \} - \left \{\frac{2n}{5d}\right \} \right ),$$$$(c_2-c_1)+(c_3-c_1)=(c_1+c_2+c_3)-3c_1=\sum_{d|n}\mu(d) \left (3\left \{\frac{n}{5d}\right \} - \left \{\frac{3n}{5d}\right \} \right ).$$ Let us to introduce the next quantities for $i=0,1,2,3,4$: $$v_i(n)=\sum_{d|n,n/d\equiv i \mod 5} \mu(d).$$Of course, it is true that $\sum_{i=0}^4 v_i(n)=0$ for any $n>1$ From the previous equalities we have $$c_2-c_1=v_3(n)+v_4(n), (c_2-c_1)+(c_3-c_1)=v_2(n)+v_3(n)+2v_4(n)$$and $$c_1-c_2=v_1(n)+v_2(n), c_1-c_3=v_1(n)+v_3(n), c_2-c_3=v_2(n)-v_3(n),$$so $$S(n)=\sum_{1\le i<j\le 5}(c_i-c_j)^2=4(v_1(n)+v_2(n))^2+2(v_1(n)+v_3(n))^2+2(v_2(n)-v_3(n))^2.$$ Let us notice that if $5||n$ then $v_i(n)=-v_i(n/5)$ for $i>0$, so $S(n)=S(n/5)$ and we can consider only the case $5\not |n$. Looking at definitions of $v_i$ we see that all depends on remainders of reprocials of prime divisors of $n$ modulo $5$. Let $n=\prod_{i=1}^s p_i^{\alpha_i}$, and $r_i$ be remainder of $p_i^{-1}$ modulo $5$. We consider several cases. 1) $r_j=1$ for some $j$. Then for any $i$ we have $$v_i(n)=\sum_{d|n,n/d\equiv i \mod 5} \mu(d)=(1+\mu(p_i))v_i(n/p_i)=0$$and $S(n)=0$. Hence we suppose that possible values of $r_i$ are $2,3,4$. 2) $r_j=2, r_k=3$ for some $j,k$. If $n=p_jp_kn'$ then $$v_1(n)=2v_1(n')-v_2(n')-v_3(n'),$$$$v_2(n)=2v_2(n')-v_1(n')-v_4(n'),$$$$v_3(n)=2v_3(n')-v_1(n')-v_4(n'),$$$$v_4(n)=2v_4(n')-v_2(n')-v_3(n'),$$hence $$v_1(n)+v_2(n)=v_1(n')+v_2(n')-v_3(n')-v_4(n')=2(v_1(n')+v_2(n')),$$$$v_1(n)+v_3(n)=v_1(n')+v_3(n')-v_2(n')-v_4(n')=2(v_1(n')+v_3(n')),$$$$v_2(n)-v_3(n)=2(v_2(n')-v_3(n')),$$and $S(n)=4S(n')$. 3) $r_j=r_k=4$ for some $j\not =k$. Then $$v_1(n)=2v_1(n')-2v_4(n'),$$$$v_2(n)=2v_2(n')-2v_3(n'),$$$$v_3(n)=2v_3(n')-2v_2(n'),$$$$v_4(n)=2v_4(n')-2v_1(n'),$$hence $$v_1(n)+v_2(n)=2v_1(n')+2v_2(n')-2v_3(n')-2v_4(n')=4(v_1(n')+v_2(n')),$$$$v_1(n)+v_3(n)=2v_1(n')+2v_3(n')-2v_2(n')-2v_4(n')=4(v_1(n')+v_3(n')),$$$$v_2(n)-v_3(n)=4(v_2(n')-v_3(n')),$$and $S(n)=16S(n')$. 4) $r_j=r_k=r_l=r_m=2$ for some paiwise distinct $j,k,l,m$. If $n=p_jp_kp_lp_mn'$, then $$v_1(n)=2v_1(n')-4v_3(n')+6v_4(n')-4v_2(n'),$$$$v_2(n)=2v_2(n')-4v_1(n')+6v_3(n')-4v_4(n'),$$$$v_3(n)=2v_3(n')-4v_4(n')+6v_2(n')-4v_1(n'),$$$$v_4(n)=2v_4(n')-4v_2(n')+6v_1(n')-4v_3(n'),$$hence $$v_1(n)+v_2(n)=-2v_1(n')-2v_2(n')+2v_3(n')+2v_4(n')=-4(v_1(n')+v_2(n')),$$$$v_1(n)+v_3(n)=-2v_1(n')-2v_3(n')+2v_2(n')+2v_4(n')=-4(v_1(n')+v_3(n')),$$$$v_2(n)-v_3(n)=4(v_3(n')-v_2(n')),$$and $S(n)=16S(n')$. 5) $r_j=r_k=r_l=r_m=3$ for some paiwise distinct $j,k,l,m$. If $n=p_jp_kp_lp_mn'$, then $$v_1(n)=2v_1(n')-4v_2(n')+6v_4(n')-4v_3(n'),$$$$v_2(n)=2v_2(n')-4v_4(n')+6v_3(n')-4v_1(n'),$$$$v_3(n)=2v_3(n')-4v_1(n')+6v_2(n')-4v_4(n'),$$$$v_4(n)=2v_4(n')-4v_3(n')+6v_1(n')-4v_2(n'),$$hence $$v_1(n)+v_2(n)=-2v_1(n')-2v_2(n')+2v_3(n')+2v_4(n')=-4(v_1(n')+v_2(n')),$$$$v_1(n)+v_3(n)=-2v_1(n')-2v_3(n')+2v_2(n')+2v_4(n')=-4(v_1(n')+v_3(n')),$$$$v_2(n)-v_3(n)=4(v_3(n')-v_2(n')),$$and $S(n)=16S(n')$. We need to check some cases: a) $s=0$, $n=1: S(n)=6\geq 2^1$, b) $s=1$, $r_1=2,3$ or $4: S(n)\geq 4=2^2$, c) $s=2$, $\{r_1,r_2\}=\{2,2\}$, or $\{2,4\}$, or $\{3,3\}$, or$\{3,4\} : S(n)\geq 8=2^3,$ d) $s=3$, $\{r_1,r_2,r_3\}=\{2,2,2\}$, or $\{2,2,4\}$, or $\{3,3,3\}$, or $\{3,3,4\}: S(n)\geq 16=2^4.$ e) $s=4$, $\{r_1,r_2,r_3,r_4\}=\{2,2,2,2\}$, or $\{2,2,2,4\}$, or $\{3,3,3,3\}$, or $\{3,3,3,4\}: S(n)\geq 32=2^5.$ Putting together all above ingredients and using mathematical induction by $s$ we get that $S(n)\geq 2^{s+1}$ for $5\not |n$ and $S(n)\geq 2^{s}$ for any positive integer $n$, q.e.d. P.S. We could easily see, that if we take, for example $17$ different primes $q_i\equiv 2 \mod 5$ and $17$ different primes $r_i\equiv 3 \mod 5$ and $n=35\prod_{i=1}^{17} q_ir_i$ then $S(n)$ is exactly equal to $2^{36}$. Also for some constant $c$ it is true that $S(n)\leq c4^s$ for any positive integers $n$ with exactly $s$ different prime divisors. This is an evident fact using trivial estimate $v_i(n)\leq 2^s$ but we cannot do better for $n$ that equal to product of different primes which are equivalent $4$ modulo $5$.
12.03.2021 05:49
Solution: BASH BASH WOW! Fixed @below Note $\sum\limits_{i=1}^k c_i=\sum\limits_{S\subseteq T} (-1)^{|S|} \lfloor \frac{kn}{5\prod\limits_{p\in S} p}\rfloor$. We make a few observations: If $25\mid n$, we can see that $\sum\limits_{i=1}^k c_i=\frac k5 \varphi(n)$, and $c_i=\frac{\varphi(n)}{5}$, contradiction. Now, note $\sum\limits_{i=1}^k c_i-\frac k5 \varphi(n) = \sum\limits_{S\subseteq T} (-1)^{|S|} \lfloor \frac{kn}{5\prod\limits_{p\in S} p} \rfloor - \frac{kn}{5\prod\limits_{p\in S} p} = - \sum\limits_{S\subseteq T} (-1)^{|S|} \{ \frac{kn}{5\prod\limits_{p\in S} p} \}$. Let $x_i=c_i-\frac{\varphi(n)}{5}$. Then $x_k= - \sum\limits_{S\subseteq T} (-1)^{|S|}( \{ \frac{kn}{5\prod\limits_{p\in S} p} \}-\{ \frac{(k-1)n}{5\prod\limits_{p\in S}p} \}$, so $|x_k-x_l| = |\sum\limits_{S\subseteq T} (-1)^{|S|} \{ \frac{kn}{5\prod\limits_{p\in S} p} \} - \{ \frac{(k-1)n}{5\prod\limits_{p\in S} p} \}-\{ \frac{ln}{5\prod\limits_{p\in S} p} \} + \{ \frac{(l-1)n}{5\prod\limits_{p\in S} p}\}| $ Now, let's list some observations: If $5\mid n$, this prime factor can be "ignored", as we only look at $5\in S$. We redefine $$P=\prod_{p\in T, p\ne 5} p$$and $$Q=\frac{n}{5^{\nu_5(n)} P}$$ Hence $|x_k-x_l| = |\sum\limits_{S\subseteq T} (-1)^{|S|} \{ \frac{Qk\prod\limits_{p\in S} p}{5} \} - \{ \frac{(k-1)Q\prod\limits_{p\in S} p}{5} \} - \left\{\frac{Ql\prod\limits_{p\in S} p}{5} \right\} + \{ \frac{(l-1)Q\prod\limits_{p\in S} p}{5}\}| $ From now on we assume $n$ has $\omega(n)$ prime factors and we wish to show that $\sum\limits_{1\le i<j\le 5} (x_i-x_j)^2\ge 2^{\omega(n)+1}$.
The rest is really standard, annoying casework.
26.06.2021 10:51
@above, "Multiplying $n$ by the same prime factor simply exchange $x_1,x_2,x_3,x_4$, so we assume $n$ is squarefree". I don't understand. Please explan about $D_i$.
26.06.2021 11:28
This one is actually 2020CMO3.
19.08.2021 04:25
For each $k\in\mathbb N$ and $1\leq i\leq 5$ define $$S^i_k=\{m:(i-1)n\leq m\leq in\}$$Obviously $f(m)=k-m$ is a bijection between $S^i_k$ and $S^{6-i}_k$. Hence $|S_k^i|=|S_k^{6-i}|$. Meanwhile, $c_i=|S^i_n|$. Notice that each integer $m$ in the interval $[0,\frac{n}{5}]$ belongs to a unique $S^1_k$ where $k|n$, namely $k=\frac{n}{(n,m)}$. Therefore, $$\sum_{d|n}|S_k^1|=\lfloor\frac{n}{5}\rfloor$$Mobius inversion formula gives $$c_1=c_5=|S_n^1|=\sum_{d|n}\mu(d)\lfloor\frac{n}{5d}\rfloor$$Similarly \begin{align*} c_2=c_4&=|S_n^2|\sum_{d|n}\mu(d)\left(\lfloor\frac{2n}{5d}\rfloor-\lfloor\frac{n}{5d}\rfloor\right)\\ c_3&=|S_n^3|\sum_{d|n}\mu(d)\left(\lfloor\frac{3n}{5d}\rfloor-\lfloor\frac{2n}{5d}\rfloor\right) \end{align*}Therfore, \begin{align*} S(n)=&\sum_{1\leq i\leq j\leq 5}(c_i-c_j)^2\\&=2(c_1-c_3)^2+2(c_2-c_3)^2+4(c_1-c_2)^2\\ &=2\left(\sum_{d|n}\mu(d)\left(\lfloor\frac{3n}{5d}\rfloor-\lfloor\frac{2n}{5d}\rfloor-\lfloor\frac{n}{5d}\rfloor\right)\right)^2+2\left(\sum_{d|n}\mu(d)\left(\lfloor\frac{3n}{5d}\rfloor+\lfloor\frac{n}{5d}\rfloor-2\lfloor\frac{2n}{5d}\rfloor\right)\right)^2+4\left(\sum_{d|n}\mu(d)\left(\lfloor\frac{2n}{5d}\rfloor-2\lfloor\frac{n}{5d}\rfloor\right)\right)^2 \end{align*}Define $f_1(n),f_2(n),f_3(n)$ to be the expression in the three small brackets, i.e. $$f_1(n)=\lfloor\frac{3n}{5d}\rfloor-\lfloor\frac{2n}{5d}\rfloor-\lfloor\frac{n}{5d}\rfloor=\begin{cases}0&\frac{n}{d}\equiv 1,3,5\pmod 5\\1&\frac{n}{d}\equiv 2,4\pmod 5\end{cases}$$$$f_2(n)=\lfloor\frac{3n}{5d}\rfloor+\lfloor\frac{n}{5d}\rfloor-2\lfloor\frac{2n}{5d}\rfloor=\begin{cases}0&\frac{n}{d}\equiv 1,4,5\pmod 5\\ 1&\frac{n}{d}\equiv 2\pmod 5\\ -1&\frac{n}{d}\equiv 3\pmod 5\end{cases}$$$$f_3(n)=\lfloor\frac{2n}{5d}\rfloor-2\lfloor\frac{n}{5d}\rfloor=\begin{cases}1&\frac{n}{d}\equiv 3,4\pmod 5\\ 0&\frac{n}{d}\equiv 1,2,5\pmod 5\end{cases}$$and $g_i(n)=\sum_{d|n}\mu(d)f_i(\frac{n}{d})$ Now, if $5|n$ we can simply replace $n$ by $\frac{n}{5}$ and obviously $S(n)=S(\frac{n}{5})$. Therefore we only have to deal with the case where $n$ has $35$ or $36$ prime factors, all of which are distinct from $5$. We distinguish into three cases, let $S$ be the set of square-free divisors of $n$. Case I: $p|n$ where $p\equiv 1\pmod 5$ Suppose $n=mp^\alpha$ where $(m,n)=1$. Let $S_m$ be the set of square-free divisors of $m$ and let $S_p=S\setminus S_m$. Then obviously $\varphi(d)=pd$ is a bijection from $S_m$ to $S_p$. Meanwhile $\mu(\varphi(d))=-\mu(d)$, and $f_1(\frac{n}{d})=f_1(\frac{n}{\varphi(d)})$ hence $$g_1(n)=\sum_{d|m}\mu(d)f_i(\frac{n}{d})+\mu(\varphi(d))f_i(\frac{n}{\varphi(d)})=0$$similarly $g_2(n)=g_3(n)$, hence $c_1=c_2=c_3=c_4=c_5$, contradiction. Case II: $p|n$ where $p\equiv 4\pmod 5$ Let $n=mp^{\alpha}$, it is easy to see that we can assume $\alpha=1$, we claim that $$S(n)=4S(m)\hspace{20pt}(1)$$Indeed, define $S_m$ and $S_p$ as in the previous case. Notice that if $d\in S_m$ and $\frac{m}{d}\equiv 2,4\pmod 5$ then $d$ contributes $\mu(d)$ to $g_1(n)$, if $d\in S_m$ and $\frac{m}{d}\equiv 1,3\pmod 5$ then $pd$ contributes $-\mu(d)$ to $g_1(n)$. Therefore, $$g_1(n)=\sum_{d|n}\mu(d)f_i(\frac{n}{d})=\sum_{d|m,d\equiv 2,4\pmod 5}\mu(d)-\sum_{d|m,d\equiv 1,3\pmod 5}=2\sum_{d|m,d\equiv 1,3\pmod 5}\mu(d)=2g_1(m)$$the last line follows from $\sum_{d|m}\mu(d)=0$. We prove $(1)$ by adding similar expressions for $g_2,g_3$. Therefore, we are easily done by induction. Case III:All prime factors of $n$ are congruent to $2$ or $3$ modulo $5$ Proof. We show the assertion for all $n$ which has $4k$ prime factors. The case $k=1$ is straightforward. Now for the general case, notice that if $\frac{n}{d_1}\equiv 2\pmod(5)$ and $\frac{n}{d_2}\equiv 4\pmod 5$ then $\mu(d_1)+\mu(d_2)=0$. Therefore, $$g_1(n)=(x_n-z_n)^2$$where $w_n,x_n,y_n,z_n$ denote the number of divisors in $S$ which are congruent to $1,2,3,4\pmod 5$ respectively. Similarly, $$g_2(n)=(x_n-y_n)^2$$$$g_3(n)=(y_n-z_n)^2$$Since $k\geq 2$ there are at least $4$ prime factors which are all congruent to $2$ or $3$, say $2$ modulo $5$. Suppose they are $p_1,p_2,p_3,p_4$, we can assume $v_{p_i}(n)=1$, let $w_{n-i}$ be the number of square-free divisors of $\frac{n}{p_1...p_i}$ which are congruent to $1$ modulo $5$, define the other sequences similarly. We have the recurrences $$(w_m,x_m,y_m,z_m)=(w_{m-1}+y_{m-1},x_{m-1}+w_{m-1},y_{m-1}+z_{m-1},x_{m-1}+z_{m-1})$$which implies $w_m+z_m=x_m+y_m$ and straightforward computation gives $$\frac{x_n-z_n}{x_{n-4}-z_{n-4}}=\frac{x_n-y_n}{x_{n-4}-y_{n-4}}=\frac{y_n-z_n}{y_{n-4}-z_{n-4}}=4$$therefore $$S(n)=16S(\frac{n}{p_1p_2p_3p_4})$$which completes the inductive step and hence the whole proof.