How to use the sum of two squares calculator
- Enter a whole number from 0 up to 1,000,000,000,000.
- Read the prime factorization and the number of ways to write the number as a squared plus b squared with a no larger than b.
- Open the table to see every pair (a, b). If none exists, the page names the prime that blocks it.
- Use the count with signs, r2(n), if you want ordered pairs of positive and negative values.
Formula
n = a^2 + b^2 has a solution in whole numbers exactly when every prime p = 3 (mod 4) divides n to an even power
Jacobi's formula: the number of ordered integer pairs (x, y), signs included, is r2(n) = 4 (d1(n) - d3(n))
With n = 2^e x (primes 1 mod 4: p^f) x (primes 3 mod 4: q^g), r2(n) = 4 x product of (f + 1) when every g is even, otherwise 0
Each solution (a, b) with 0 < a < b gives 8 ordered pairs, which accounts for the count r2(n)
The list is found by testing every a up to the square root of n / 2 and checking whether n minus a^2 is a perfect square, so it is exact.
65, 1105 and 21
The number 65 = 5 x 13 has two representations, 1 + 64 and 16 + 49, written 1^2 + 8^2 and 4^2 + 7^2. With signs and order there are 16 ordered pairs. The number 1105 = 5 x 13 x 17 has four, 4^2 + 33^2, 9^2 + 32^2, 12^2 + 31^2 and 23^2 + 24^2, and 32 ordered pairs. The prime 1000033 is 1 mod 4 and has exactly one, 408^2 + 913^2.
The number 21 = 3 x 7 has none, since both 3 and 7 are 3 mod 4 and appear to the power 1. The number 50 = 2 x 5^2 has 1 + 49 and 25 + 25, and 1,000,000 has four ways, including 0^2 + 1000^2 and 600^2 + 800^2.
Fermat's two-square theorem
Fermat showed that an odd prime is a sum of two squares exactly when it leaves remainder 1 when divided by 4. The full rule for any number follows by multiplying: the identity (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 lets you combine representations, and a prime that is 3 mod 4 can only appear squared, because it cannot be split any further. The factor 2 is always harmless since 2 = 1^2 + 1^2.
A Pythagorean triple is the special case in which the sum of two squares is itself a square, such as 9 + 16 = 25. The Pythagorean theorem calculator finds the missing side of a right triangle once you know the other two.
Using the table
The count with signs, r2(n), is useful for lattice problems: it is the number of grid points on a circle of radius the square root of n centered at the origin. For 65 there are 16 such points, and for 1105 there are 32. A circle through many grid points is rare, and the numbers with the most points are products of many primes that are 1 mod 4.
To factor a number on its own or test whether it is prime, use the prime number calculator. To see whether a number is a square modulo a prime, which tells you which primes can divide a sum of two squares, use the Legendre and Jacobi symbol calculator.
Assumptions and limits
- The number is a whole number from 0 to 10^12, so all products stay exact.
- Pairs are listed with 0 <= a <= b. Swapping or negating a and b gives the other ordered pairs.
- Zero counts as a square, so 25 = 0^2 + 5^2 is included.
- Sums of more than two squares, such as four squares, are not covered here.
Frequently asked questions
Which numbers are a sum of two squares?
Those where every prime that leaves remainder 3 when divided by 4 appears an even number of times. So 45 = 9 x 5 works (36 + 9) and 21 does not.
Why does 3 x 3 = 9 work but 3 does not?
Because 9 = 0^2 + 3^2 uses the prime 3 squared. A single 3 cannot be split into two squares.
What does r2(n) count?
The number of pairs (x, y) of integers, positive, negative or zero, with x squared plus y squared equal to n. Order and signs both count.
How large can n be?
Up to 10^12. The search is exact and takes under a second at that size.