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)$

Question

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.

Answer 1

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

Answer 2

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 .

Answer 3

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!