<s>[INST] 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.
 [/INST] 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!
</s>