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.

$\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.
