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.


3 Answers 3


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


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.

  • $\begingroup$ what do you mean by sufficiently large ? $\endgroup$
    – Raheel
    Jul 31, 2020 at 3:17
  • $\begingroup$ Actually "sufficiently large" is not the right phrase, I meant "suitable". I've edited. $\endgroup$ Jul 31, 2020 at 3:24
  • $\begingroup$ @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 . $\endgroup$ Jul 31, 2020 at 13:09
  • 1
    $\begingroup$ Oh! I see , beautiful proof, I learned a lot.. $\endgroup$ Jul 31, 2020 at 16:58
  • 1
    $\begingroup$ Thanks @Shubhangi. Wait for a little I am still writing the conclusion part :) $\endgroup$ Jul 31, 2020 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<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!

  • $\begingroup$ Great! Keep it up! Just note that your both the cases can be combined together . $\endgroup$
    – Raheel
    Jul 31, 2020 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 .

  • $\begingroup$ Thank You so much! I think I got it .. $\endgroup$ Jul 31, 2020 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.