# Integer solutions to $x^2+y^2=N$?

This is not homework; but I am completely lost on how to go about handling this especially for large N

-
What's this? Some weak form of Fermant's theorem? :) – Diego Dec 21 '11 at 22:08
Yes -- N does not have to be a square number – HSE Dec 21 '11 at 22:11
Solving this problem algorithmically for very large $N$ is difficult, just like factorization of very large numbers is difficult. Solving your problem is essentially the same as the problem of factoring $N$ over the Gaussian integers. – André Nicolas Dec 21 '11 at 22:12
Just wondering, given N, is there a way to count the number of integer solutions for the equation? – NoChance Dec 22 '11 at 10:31
Is it just me or there is no verb in this question? Whether the OP is interested in the number of solutions, or in a way to find one or all solution, or in whether there is a solution - I guess that's for us to decide? – Bruno Joyal Dec 27 '11 at 19:33

if you want integer solutions, then the primes of the form $4k+3$ dividing $N$ must occur to an even power. To see this you must show that

i) the product of a sum of two squares is a sum of two squares

ii) an odd prime $p$ is the sum of two squares iff $p\equiv1\mod 4$

i) $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2$ (think of the norms of complex numbers)

-
"A Discipline of Programming" by Edsger W. Dijkstra has a chapter on an algorithm to solve this. I don't know how efficient it is, but the book is a great read IMHO. – marty cohen Dec 21 '11 at 23:24
yoyo wrote: > > If you want integer solutions, then N must have an even number of prime factors > of the form 4k+3. I don't have comment privileges; but this condition, although necessary, is not sufficient. For example 21, comprising the factors 3 and 7, is not representable as the sum of two squares of integers. The necessary and sufficient condition is that each factor of the form $4k+3$ of $N$ must occur to an even power. – John R Ramsden Dec 22 '11 at 22:03

Me again. An algorithm, claimed to be efficient, for finding solutions can be found here.

Also, a recent ArXiV paper claims (based on the abstract) to generalize H.J.S. Smith's algorithm for the same based on palindromes.

-

Here are a few possible simplifications of the computational complexity which might help without having to explicitly write $N$ as a product of prime factors. If $N$ is even and $N = x^2 + y^2$ for integers $x$ and $y$, then $\frac{N}{2} = (\frac{x+y}{2})^2 + (\frac{x-y}{2})^2,$ and both these terms are integers, as $x$ and $y$ must have the same parity. On the other hand, if $M$ is an integer with $M = a^2 +b^2$ for integers $a$ and $b,$ then $2M = (a+b)^2 + (a-b)^2.$ Hence if $N$ is even, we can replace $N$ by $\frac{N}{2},$ and the answer to the question " is $N$ a sum of two integer squares" is unchanged, though computationlly easier. Now suppose that $N = LM$ for integers $L$ and $M$ with $1 < L < N.$ If ${\rm gcd}(L , M) = h >1,$ then $N$ is a sum of two integer squares if and only if $\frac{N}{h^2}$ is. If ${\rm gcd}(L,M) = 1,$ then $N$ is a sum of two integer squares if and $L$ and $M$ both are.

-

Ok, here's my attempt at this. The wikipedia page got better results though :(

1. define f(x,y) = x^2+y^2
2. define g(n) = N
3. rewrite the equation to look like f(x,y) = g(n)
4. Now use a pullback from category theory. You go backwards in the functions.
5. It starts like a pair (k,k), where k=k.
6. then left side of the pair tries to find x and y, while right side tries to find n.
7. the left side is more complicated. First consider a+b expression. You can split number N to two parts so that a+b = N (this N comes from left side of pair). Any splitting is ok. Think of range [0..N] and split it to [0..a] and [a..N]. Choose freely both a and b, but so that a+b=N.
8. Now you have chosen the a and b. These are numbers representing the area of a square. Now to find x and y, you just move from the area of square to the length of the side of the square. $x=\sqrt a$, $y=\sqrt b$ This will result in x : R, y : R. These are not in $N$, unless you choose a and b in certain way. So the process of choosing a and b fails if length of square's side is not integers.
9. Problem with algorithms solving this is that there are many different ways to choose the splitting, especially when the numbers are large. And then later in the process, many of those possible solutions (a,b) will fail to materialize.
10. There is one additional trick available which lets us narrow the solutions. The right side g(n)=N, can be rewritten as if it were a constant. Split $g : N \rightarrow N$ to $! : N \rightarrow 1$ and $g_1 : 1 \rightarrow N, g_1=N$. Now this might seem like technicality, but it gives us one big advantage - the g can only give us single element of $N$. So all values of n are in the same area inside N in right side. If we consider tuples (x,y,n) which are the solutions to the equation, large number of them are the same, and we only need to consider (x,y) as a shorthand notation for (x,y,N). This is only necessary because we chose to use a function g originally and did not regognize it to be a constant.
11. Now there is also intersection operation on powersets involved. To find out which (x,y,n) tuples are solutions of the equation, the projections (x,y,n) |-> (x,y) and (x,y,n) |-> (n) need to be "inverted" using the pullback. Left and right side of the equation gave us "areas" of values of x, y and n which are involved, now combining those areas gives us the solution. But then we end up with two (x,y,n) (powerset) tuples, and their intersection is needed to find the solutions of the equation. The pair (k,k) needs to be considered at this stage when both (x,y,n) tuples are combined - the pairs create equivalence class on the tuples which allows us to find several/all solutions to the equation. Jumping from left side to right side and back to left side of the equation might end up in different elements, and if we started from a solution to the equation, the new elements are again a solution to the equation.
12. Now going further than this likely requires breaking $\sqrt a$ and $\sqrt b$ to something smaller and discovering more of it's properties. (I will still need to read the wikipedia page properly to see how they did it)
-
"Now use a pullback from category theory. You go backwards in the functions." Huh? (I stopped reading there.) – Bruno Joyal Dec 27 '11 at 19:31
You stopped reading exactly the correct place. Those two are the solution to the problem. All the rest is just minor details derived from those two. – tp1 Dec 27 '11 at 21:47
I can't make much sense of this (it is not even in proper mathematical notation) but I think this is a complicated version of brute force...a complicated version of simply "trying all squares of numbers less than $\sqrt{N}$ to see which work". – fretty Feb 25 '12 at 17:17
Man this looks like a great method to boost performance on my old VX. You should post this over at reddit.com/r/vxjunkies, the people over there would definitely appreciate it. – Zook Apr 25 '14 at 14:03