### Representing integers as the sum of two squares

Almost 400 years ago, Pierre de Fermat stated that every odd prime of the form `4k+1` can be expressed as the sum of two squares:

`p = x^2 + y^2`

with integers `x` and `y`, if and only if

`p ≡ 1 mod 4`

Later on, around the year 1747, Leonhard Euler was able to prove Fermat's statement correct.

# Overview In this post we present a recursive algorithm for finding all the possible representations, as a sum of two squares, for any given integer that can be expressed this way.

For example, if `n=12345678910111213`, we can represent it as a sum of two squares in 4 different ways:

`12345678910111213 = 1251082^2 + 111104067^2` `12345678910111213 = 13508317^2 + 110286918^2` `12345678910111213 = 52418877^2 + 97969078^2` `12345678910111213 = 64959738^2 + 90143837^2`

If the prime factorization of a number is known, it can be verified if the number is expressible as a sum of two squares by checking each prime factor modulo 4. If a prime factor is congruent to `3 mod 4` , then its power must …

`p = x^2 + y^2`

with integers `x` and `y`, if and only if

`p ≡ 1 mod 4`

Later on, around the year 1747, Leonhard Euler was able to prove Fermat's statement correct.

# Overview In this post we present a recursive algorithm for finding all the possible representations, as a sum of two squares, for any given integer that can be expressed this way.

For example, if `n=12345678910111213`, we can represent it as a sum of two squares in 4 different ways:

`12345678910111213 = 1251082^2 + 111104067^2` `12345678910111213 = 13508317^2 + 110286918^2` `12345678910111213 = 52418877^2 + 97969078^2` `12345678910111213 = 64959738^2 + 90143837^2`

If the prime factorization of a number is known, it can be verified if the number is expressible as a sum of two squares by checking each prime factor modulo 4. If a prime factor is congruent to `3 mod 4` , then its power must …