EGMO 2014/P3 : Prove that there exist infinitely many positive integers $n$ such that $\omega(n) = k$ and $d(n)$ does not divide $d(a^2+b^2)$ We denote the number of positive divisors of a positive integer $m$ by $d(m)$ and the number of distinct prime divisors of $m$ by $\omega(m)$. Let $k$ be a positive integer. Prove that there exist infinitely many positive integers $n$ such that $\omega(n) = k$ and $d(n)$ does not divide $d(a^2+b^2)$ for any positive integers $a,b$ satisfying $a+b=n$.
My progress: Really beautiful but hard  problem!
For $k=1$,we can take $n=2^{p-1}$, where p is an odd prime. Let's say for some $a+b=n$ and write $a=2^ke$ and $b=2^kf$ with $e, f$ odd and $0\le k<p-1$. If $d(n)|d(a^2+b^2)$, then$$p|d \left ( 2^{2k+1}\cdot \dfrac{e^2+f^2}{2} \right )=2^{2k+2}\cdot d\left ( \dfrac{e^2+f^2}{2} \right )$$.
So $p|d\left (\dfrac{e^2+f^2}{2}\right) $ .Now, for $p$ to divide $d\left (\dfrac{e^2+f^2}{2}\right) $, we should have $\left (\dfrac{e^2+f^2}{2}\right)=l^{p-1}\cdot x, l $ is a prime and $gcd(l,x)=1$. But  note that both 2 and 3 does not divide $\left (\dfrac{e^2+f^2}{2}\right)$. But Max$(a^2+b^2)=4^{p-1}<5^{p-1}$ .
So we are done for $k=1$ .
I thought that this would be almost same for $k>1$ , but I am not able to prove.
I have conjectured that for any $k$ we can take $n = 2^{p-1}j$ such that $j$ has only $k-1$ primes.
But no progress!Please, if possible post hints rather than solution.
Thanks in advance.
 A: $\boxed{\text{Complete solution}}$
(The merit of the following solution is that it gives an explicit construction for $n$ with given $k$ satisfying the conditions.)
Let $p_m$ denote the $m^{th}$ prime with $p_1=2,p_2=3,\ldots$ and so on. Take, for $k>1$, $$n=2^{p-1}p_2p_3\cdots p_k$$ for some suitable prime $p$ and work on it. Then $d(n)=2^{k-1}p$ and $\omega(n)=k$. The key observation is that $$d(n)\mid d(a^2+b^2)\implies p\mid d(a^2+b^2)\implies q^{p-1}\mid a^2+b^2$$ for some prime $q$. Now proceed considering different cases of $q$.
Case 1 ($q>4$)
Since $q^{p-1}\mid(a^2+b^2)$ then we have $$q^{p-1}\leq(a^2+b^2)\leq (a+b)^2=n^2=4^{p-1}p_2^2p_3^2\cdots p_k^2$$ Since $q>4$ we can choose sufficiently large prime $p$ such that $$q^{p-1}>4^{p-1}p_2^2p_3^2\cdots p_k^2$$ which is a contradiction! Hence for sufficiently large prime $p$, $n$ satisfies the condition.
Case 2 ($q=3$)
Since $-1$ is not a quadratic residue modulo $3$, $3^{p-1}\mid a^2+b^2$ implies $3^{p-1}\mid a^2,3^{p-1}\mid b^2$. This implies $3^{\frac{p-1}{2}}\mid a$ and $3^{\frac{p-1}{2}}\mid b$ which gives $$3^{\frac{p-1}{2}}\mid (a+b)=n$$ Take $p>3$ then we get $v_3(n)\geq 2$ but by construction $v_3(n)=1$. So for $p>3$, $n$, as constructed, satisfies the conditions.
Case 3 ($q=2$)
then we get $2^{p-1}\mid a^2+b^2$ and also by construction $2^{p-1}\mid n^2=(a+b)^2=a^2+b^2+2ab$. This implies $2^{p-2}\mid ab$. Then write $a=2^r\alpha$ and $b=2^s\beta$ where $r,s$ are both odd. Then $p-1=v_2(n)=v_2(a+b)=\mathrm{min}(r,s)$. Therefore $r\geq p-1$ and $s\geq p-1$. This implies $v_2(ab)=r+s\geq 2(p-1)$. Or $v_2(2ab)\geq 2p-1$. On the other hand $v_2(n^2)=2p-2$. So $v_2(a^2+b^2)=v_2(n^2-2ab)=\mathrm{min}(v_2(2ab),v_2(n^2))=2p-2$. Now try to prove why this will lead you to a contradiction!
Remark:
For establishing that there are infinitely many $n$ for a given $k$ we can consider numbers of the form $$2^{p-1}p_{m+2}p_{m+3}\cdots p_{m+k}$$ for $m\geq0$ and suitable primes $p$. The proof will be analoguous.
A: I couldn't do this solution without @Raheel 's hint. It was all about $5 \pmod 6$ ! Also, I will be really grateful if someone proof reads it?Thanks in advance.
Case 1  : For $k=1$,we can take $n=2^{p-1}$, where p is an odd prime. Let's say for contradiction, there exist some $a$ and $b$ such that $a+b=n$ and  $d(n)|d(a^2+b^2)$ . Let $a=2^ke$ and $b=2^kf$ where $e, f$ odd and $0\le k<p-1$.  $d(n)|d(a^2+b^2)$, then$$p|d \left ( 2^{2k+1}\cdot \dfrac{e^2+f^2}{2} \right )=2^{2k+2}\cdot d\left ( \dfrac{e^2+f^2}{2} \right )$$.
Since $e,f$ are odd we have $e^2+f^2 \equiv 2\pmod 4$ .
Now, since $0\le k < {p-1} \implies 0\le 2k <2(p-1) \implies 0 \le 2k+2 < 2p$ and also $2k+2 \ne p$ ( as $p$ is odd) , we have,  $$p|d\left (\dfrac{e^2+f^2}{2}\right) $$ .Now, for $p$ to divide $d\left (\dfrac{e^2+f^2}{2}\right) $, we should have $\left (\dfrac{e^2+f^2}{2}\right)=l^{p-1}\cdot x, l $ is a prime and $gcd(l,x)=1$.
Now since $3\nmid e$ and $3\nmid f$, by modulo $3$ , we get that $3 \nmid \left (\dfrac{e^2+f^2}{2}\right)$.
But  note that both 2 and 3 does not divide $\left (\dfrac{e^2+f^2}{2}\right)$. So we should $\left (\dfrac{e^2+f^2}{2}\right)\ge 5^{p-1}$
But Max$(a^2+b^2)=4^{p-1}<5^{p-1}$ . A contradiction!
So we are done for $k=1$ .
Case 2 : For $k>1$.
Consider $n=2^{p-1}\cdot s$ , where $s \equiv 5 \pmod 6$ and $w(s)=k-1$ .
Now, note that $w(n)=k$ and $d(n)=p\cdot d(s)$.
Let's say for contradiction, there exist some $a$ and $b$ such that $a+b=n=2^{p-1}\cdot s$ and  $d(n)|d(a^2+b^2)$.
Using the same reasoning like we did for $k=1$ case , let $a=2^ke$ and $b=2^kf$ where $e, f$ odd and $0\le k<p-1 $ $\implies p|d\left (\dfrac{e^2+f^2}{2}\right) $
Hence, we should have $\left (\dfrac{e^2+f^2}{2}\right)=l^{p-1}\cdot x,l $ is a prime and $gcd(l,x)=1$.
Now, here comes the $5 \pmod 6$ part! Since, both $2$ and $3$ does not divide $\left(\dfrac{e^2+f^2}{2}\right)$ ,and so we should have $\left (\dfrac{e^2+f^2}{2}\right)\ge 5^{p-1}$
But Max$(a^2+b^2)=4^{p-1}<5^{p-1}.$  A contradiction!
And we are done!
A: Well.. You are really very close! Here is another hint ( which guides you to a totally different route than the previous answer  but does solves the problem )
Let $n = 2^{p-1}t$, where $t \equiv 5 \pmod 6$, $\omega(t) = k-1$ ( take a very large p )
Let $a+b=n$ and $a^2+b^2=c$. We claim that $p \nmid d(c)$ which solves the problem.
Think why did we take $5 \pmod 6$ ? the same observation you got for k=1 , try it and you will get a bound for $c$ .
Finally see the powers of 2 in $c$.
Ps:This hint is  mine but the route which this hint leads to is a solution  from aops but I am contributing it here  so that it helps you and other users who are interested in this problem .
