# Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.

Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.($a^2+b^2$, is same $b^2+a^2$), $n \in \mathbb{N}.$

I have proved the above question which appeared in one of the Math-Olympiad. And I do know the solution. Sharing the question only because the question has a cute solution.

-
RMO or INMO by any chance? –  Soham Chowdhury May 17 '13 at 13:46
@SohamChowdhury: Yes. Its from RMO. –  Inceptio May 17 '13 at 14:59

• Let $n = 4x^4$, we have: $$n(n+1) = (4x^4)^2 + (2x^2)^2 = (4x^4-2x^2)^2 + (4x^3)^2$$
• Let $n = (u^2 + v^2)^2$, we have \begin{align} n(n+1) = & ((u^2 + v^2)^2)^2 + (u^2+v^2)^2\\ = & (u^4 - 2uv - v^4)^2 + (2uv^3-v^2+2u^3v+u^2)^2\\ = & (u^4 + 2uv - v^4)^2 + (2uv^3+v^2+2u^3v-u^2)^2 \end{align}
• Let $n = (x+y)^2 + (2xy)^2$, we finally have an example that $n$ is not a square: \begin{align} n(n+1) = & (4x^2y^2+2xy+y^2-x^2)^2 + (4x^2y+y+x)^2\\ = & (4x^2y^2+2xy-y^2+x^2)^2 + (4y^2x+y+x)^2 \end{align}
-
(+1) This is very close to my answer: $4x^4=(k+1)^2\Rightarrow k=2x^2-1\ldots$ –  P.. May 12 '13 at 7:07
Very nice (+1). –  Inceptio May 14 '13 at 6:55

Let $n=t^2$
$n(n+1)=(t^2)^2+t^2$

Also $t^4+t^2=(t^2-1)^2+3t^2-1$ and $3t^2-1=k^2$ for infinitely many k . (It is a Pell like equation and 3 is odd.)

-

Pretty happy with approaches. Considering $n$ as a square gives one fine way.

Consider $n=m^2=p^2+q^2$

Now, $n(n +1)= (p^2+q^2) (m^2+1)$

$=(pm+q)^2+(qm-p)^2$

Note that they are two distinct ways.

Thus, for example, $m=5k, p=4k,q=3k$

$n(n +1)= (25k^2)^2+ (5k)^2=(15k^2+4k^2)^2+(20k^2-3k^2)^2$

And we know that there are infinite numbers of the form $n=p^2+q^2$ (Pythagorean Triplets)

-

If $n$ is a square then $n(n+1)$ is a sum of two squares, $n(n+1)=n^2+n$. If $n$ is a square of the form $n=(k+1)^2$ with $2k+2$ a square then $n(n+1)$ can be written as a sum of two squares in another way: $$n(n+1)=(k+1)^2(k^2+2k+2)=(k+1)^2k^2+(k+1)^2(2k+2).$$ Of course there are infinitely many $k\in\mathbb N$ such that $2k+2$ is a square.

-

If $n=t^2$ is a square, all odd prime factors of $n+1$ are equal to $1 \mod 4$, and by using the Chinese remainder theorem for equations $t^2+1=0 \mod p_i$ it can be arranged that $n+1$ is divisible by many different such primes.

The conclusion is that for any $k$, there is an arithmetic progression of values of $t$ such that $n(n+1)$ has more than $k$ different representations as sum of two squares, when $n=t^2$. This is a denser set of $n$ than the other solutions, and it would be interesting to see if there is an explicit construction that has higher density, possibly as high as linear (ignoring logarithmic factors).

-
I don't believe an explicit construction is known, but a result of Hooley (1974) shows that $n$ and $n+1$ are both sums of two squares with frequency $\Theta(x/\log x)$ for $n \le x$. I believe it can be strengthened to arithmetic progressions, so that one can build up arbitrarily many distinct representations. –  Erick Wong May 12 '13 at 7:42
Actually I suppose the density here is so high that one cannot help but have many representations in most values of $n$ and $n+1$. For instance, only $O(\sqrt{x/\log x})$ numbers up to $x$ admit a unique representation as a sum of two squares. –  Erick Wong May 12 '13 at 8:03
Hooley's result looks optimal up to a bounded positive factor, and hints that the frequency for the $n(n+1)$ form of the problem ought to be $Cx/\sqrt{\log x}$. @ErickWong –  zyx May 12 '13 at 20:04
That $n$ and $n+1$ both have to meet the condition also explains why it is hard to do better than $x^{1/2}$ with an explicit construction. –  zyx May 12 '13 at 20:15
I had the unfair advantage of reading Hooley's paper which explicitly uses bounds on $\sum r_2(n(n+1))$... :). –  Erick Wong May 12 '13 at 20:16