Prove that there exists a positive integer $N$ such that the equation x^2 + y^2 = N has at least 2005 solutions in non-negative integers $x$ and $y$.

Question

Hint: Try to construct a bunch of triples that all have the same hypotenuse.

Answer 1

Let $N=5^n$. Then we find lots of solutions $(x,y)$ by letting $x$ be the absolute real and $y$ the absolute imaginary parts of $(2+i)^k(2-i)^{n-k}$.

---

Next level: In the above, $\gcd(x,y)=5^{\min\{k,n-k\}}$. Show that we can achieve $\gcd(x,y)=1$ for all $\ge2005$ distinct solutions.