Proof to find at least 2005 ordered pairs (x, y)

Question

Prove that there exists a positive integer $N$ such that there are at least 2005 ordered pairs $(x,y),$ of non-negative integers $x$ and $y$, satisfying $x^2 + y^2 = N.$

Not sure how to get going here. Is there a simple way of solving this problem using Pythagorean Triples?

Answer 1

The question is essentially about factorisation in the ring $\Bbb Z[i]$.

A really cheap way is to take $N = 5^k$ for a sufficiently large $k$.

For every $a$ in the range $[0, k]$, if we write $(1 + 2i)^a(1 - 2i)^{k - a} = x + yi$, then we have $x^2 + y^2 = 5^k$.

There will be some repetitions, but at most by a constant factor, so taking $k$ large enough will be OK.

Answer 2

There will be at least one distinct triple for every prime factor of $C$ in a Pythagorean Triple. For example, $1105$ has only $3$ factors: $(5, 13, 17)$ but has $4$ distinct triples with that value of $\sqrt{N}$. $$ f(24,23)=(47,1104,1105)\quad f(31,12)=(817,744,1105)\quad f(32,9)=(943,576,1105)\quad f(33,4)=(1073,264,1105)\quad $$

Having $2005$ factors, your $C$-value could be very large requiring arbitrary precision for over $6000$ digits but it exists. You want $N=C^2$ so it will be larger still.

Answer 3

If you're allowed to use the fact that there are infinitely many primitive Pythagorean triples, which isn't too hard to prove, or even just that there are $2005$ primitive Pythagorean triples, then you can proceed as follows. For $1\leq i\leq2005$, let $(a_i,b_i,c_i)$ be a primitive Pythagorean triple, and set $P=\prod_{i=1}^{2005}c_i$. For each $j$ from $1$ to $2005$, let $x_j=(a_j/c_j)P$ and $y_j=(b_j/c_j)P$; in other words, $x_i$ is the same product as $P$ except that the one factor $c_j$ has been changed to $a_j$, and similarly for $y_j$. Then, since $a_j^2+b_j^2=c_j^2$, we have $x_j^2+y_j^2=P^2$. Wo $N=P^2$ has $2005$ representations as a sum of two squares. These representations are all distinct, because the triples $(a_i,b_i,c_i)$ were primitive --- none is proportional to another.

Answer 4

Wolfram MathWorld reference

The number of ways to write $N$ as a distinct sum of two squares can be found by finding the prime factorisation of $N$ as $$N = 2^{a_0}p^{a_1}\cdots p^{a_s}q^{b_1}\cdots q^{b_r}$$ with $p$ of the form $4k-1$, and $q$ of the from $4k+1$.

The number of distinct ways to write $N$ as a sum of two squares is then given by $$\begin{cases}2^r-1 \quad & \text{if } n=0, a_0=0 \\ 0 & \text{otherwise}\end{cases}$$ so in order to have at least 2005 distinct ways we need $$N = 5\cdot13\cdot17\cdot29\cdot37\cdot41\cdot53\cdot61\cdot73 = 11472932050385$$ which gives us $2^{11}-1=2047$ primitive pythagorean triples.

Edit: I'm too tired to know how to factorise things, apparently. Major fix, should be right now. Checked my answer using Wolfram.