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

3 Answers

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

• what do you mean by sufficiently large ? Jul 31 '20 at 3:17
• Actually "sufficiently large" is not the right phrase, I meant "suitable". I've edited. Jul 31 '20 at 3:24
• @ShubhrajitBhattacharya , can you post some more hints, I tried it with your way but couldn't proceed. You can send your solution too, if you want to . Jul 31 '20 at 13:09
• Oh! I see , beautiful proof, I learned a lot.. Jul 31 '20 at 16:58
• Thanks @Shubhangi. Wait for a little I am still writing the conclusion part :) Jul 31 '20 at 17:00

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

• Great! Keep it up! Just note that your both the cases can be combined together . Jul 31 '20 at 13:35

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 .

• Thank You so much! I think I got it .. Jul 31 '20 at 12:42