$x^2+y^2=N$, Diophantine equation

Question

$$ x^2+y^2=N $$

$N$ integer,

Find $x,y$ integer so that the Diophantine equation is fulfilled.

If $N$ is a prime number, we can calculate all solutions very fast via Gauß reduction.

Is it also possible to calculate all solutions when $N$ is not a prime number?

Do you need to know the divisors of N, in order to find a solution?

Answer 1

It is possible.

I'll choose a relatively simple example. $N$ will be the product of two $4n+1$ different primes.

$$N=65=5\cdot 13$$

becomes

$$N=(2+i)(2-i)(3+2i)(3-2i)$$

now this product can be rearranged basically in two ways:

$$N=(2+i)(3+2i)(2-i)(3-2i)\qquad(1)$$

$$N=(2+i)(3-2i)(2-i)(3+2i)\qquad(2)$$

From (1) we get

$$N=(4+7i)(4-7i)=4^2+7^2$$

and from (2),

$$N=(8-i)(8+i)=8^2+1^2$$

However, if $n$ has a $4n+3$ prime factor with odd multiplicity, it is not possible.

Answer 2

Yes. For each prime power $p^k\mid N$ (with $p^{k+1}\nmid N$)

• If $p=2$ take $(1+i)^k$
• If $p\equiv -1\pmod 4$, we need $k$ is even (or there is no solution). Take $p^{k/2}$
• If $p\equiv 1\pmod 4$, find a solution $u^2+v^2=p$ and take in turn $(u+iv)^k$, $(u+iv)^{k-1}(u-iv)$, and so on until $(u-iv)^k$.
• For the unit take in turn $1,i,-1,-i$.

For each choice you made, multiply all these together to obtain $x+iy$. For example, consider trhe case $N=50$. Then we get $1+i$ from the factor $2$, and one of $(1+2i)^2=-3+4i$, $(1+2i)(1-2i)=5$, $(1-2i)^2=-3-4i$ for the prime $5$, and one of $1,i,-1,-i$ for the unit. This gives a total of $12$ solutions, one of them for example is $(1+i)(-3-4i)(-i)=7+i\rightarrow 7^2+1^1=50$, another is $(1+i)\cdot 5\cdot i=-5+5i\rightarrow (-5)^2+5^2=50$.