Integer solutions to x² + y² = z

Hi everyone!

As I continue working through Project Euler, I want to write a blog about another piece of general mathematical knowledge that is both interesting on its own and might be useful in some problems. Consider the following Diophantine equation:

We assume that we're given a specific number , and we need to check if there are for which the identity above holds. Then, if such numbers exist we should find them and report. Example of a problem that might need it:

Timus — 1593. Square Country. Version 2. You're given an integer . Find minimum such that .

Tl;dr.

Let , where are different prime numbers with remainder modulo , and are different prime numbers with remainder modulo . Then there are two cases. If any of is odd, there are no solutions. Otherwise there is always a solution that looks like

where and for from to . For each , to find such we need to find an integer such that , then find a minimum for . This is doable in .

And if we want to count solutions, their number is given by Jakobi's two-square theorem: The number of ways of representing as the sum of two squares is , where is the number of divisors of that have remainder modulo .

---

From exact equation to

First of all, let's solve a bit easier problem. One obvious thing we can do is to take remainder modulo on both parts:

This relaxed version is equivalent to finding such that

Hmmm... Remainders modulo arbitrary number is not the most pleasant thing to work on directly. But remainders modulo prime number are usually nice. On the other hand, if is some prime factor of and there is a solution for , it means that there will as well be a solution for with . So, let's assume to be prime, for now.

From arbitrary to prime

Now, we have another equation

where is a prime number. What's good about prime numbers is that remainders modulo prime numbers form a field (i.e. they work very similarly to rationals, and we can expect similar results to hold). For , there is a non-trivial solution . What about odd numbers ? There are two cases to consider, as the remainder of modulo is either or .

Fermat's theorem on sums of two squares tells us that for an odd prime , the solution exists if and only if has a remainder modulo . Moreover, the sum of two squares theorem tells us that the number is expressible as a sum of two squares if and only if its prime decomposition does not have a term , where , and is odd. Let's find out why.

Of course, it's not yet clear why these two cases are important. Let's assume that there is an integer such that

that is there is a remainder modulo which behaves very similarly to imaginary unit from complex numbers. Then

This reduces the initial equation to a union of linear equations

For each , except , there are possible values of , so there are a total of solutions. Noteworthy, it is always possible to find a pair of solutions such that , which means that is satisfied exactly.

How to find it? Find , and consider the minimum value of among . Due to pigeonhole principle, there will be such that . This is actually very similar to 102354I - From Modular to Rational!

Now, when does such exist and how to find it? It is known that remainders modulo have a primitive root such that its powers from to run through all possible remainders modulo . Note that for odd it always holds that

Then, if such exists we should be able to find it from

Well, technically also can be used as , but it's not that important. What's important is that it is possible to do as above only when is divisible by . In other words, when .

Now, let's think about the other case. If there is no such , we can introduce it! Now, we can formally consider numbers that look like , where is not a remainder modulo . Numbers of this kind, if treated formally, also form a field. If you're familiar with field theory, I should mention that it is isomorphic to the Galois field . If you're not familiar with it, ignore what I just wrote.

The thing now is that we can try to find all solutions in this new, extended field. And it reduces to the same union of equations

so for every , the only possible solutions are . The problem is, this time such would not be a remainder modulo , unless . Instead, it will be an "imaginary" solution. So, the only "real" solution is . It means that all solutions to

look like and . Thus,

So, if is not divisible by , there are no solutions. Otherwise reduces it to

after which similar argument could be applied. So, if is divisible by an odd power of such , there are no solutions. We're only one step away from solving the whole problem now, assuming that we know the factorization of .

Back to arbitrary

Now we need to use one more fact from complex numbers. There, we can introduce a norm

Its crucial property for this task is that it is multiplicative, that is

This gives the Brahmagupta–Fibonacci identity

from which it follows that if we can represent as a product of several several numbers that are expressible as a sum of two squares, we can use the identity above to also express as a sum of two squares. In complex number terms, it means that we will find a complex number such that .

Repeating what's written in tl'dr section, let , where are different prime numbers with remainder modulo , and are different prime numbers with remainder modulo . Then there are two cases. If any of is odd, there are no solutions. Otherwise there is always a solution that looks like

where and for from to . This result is tightly connected to the following ones:

Classification of Gaussian primes. A Gaussian integer is prime if and only if either of the following is true:

• or and the non-zero number is prime with remainder modulo ,
• is or a prime number with remainder modulo .

The result also allows to factor Gaussian integers by representing their norm as a sum of two squares in the way suggested above.

Jakobi's two-square theorem. The number of ways of representing as the sum of two squares is , where is the number of divisors of that have remainder modulo . If there is a prime divisor with remainder mod , this number is equal to . Otherwise, it is times the number of divisors of , we may interpret it that the divisor decides how much of multipliers in the product would correspond to , and how much to , after which accounts for all the possible ways to multiply with Gaussian integers units, i.e. with , , or , which accounts for all possible combinations of .