In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:
with x and y integers, if and only if
The prime numbers for which this is true are called Pythagorean primes. For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:
On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares. This is the easier part of the theorem, and follows immediately from the observation that all squares are congruent to 0 (if number squared is even) or 1 (if number squared is odd) modulo 4.
Since the Diophantus identity implies that the product of two integers each of which can be written as the sum of two squares is itself expressible as the sum of two squares, by applying Fermat's theorem to the prime factorization of any positive integer n, we see that if all the prime factors of n congruent to 3 modulo 4 occur to an even exponent, then n is expressible as a sum of two squares. The converse also holds.For a proof of the converse see for instance 20.1, Theorems 367 and 368, in: G.H. Hardy and E.M. Wright. An Introduction to the Theory of Numbers, Oxford 1938. This generalization of Fermat's theorem is known as the sum of two squares theorem.
History Albert Girard was the first to make the observation, characterizing the positive integers (not necessarily primes) that are expressible as the sum of two squares of positive integers; this was published in 1625.Simon Stevin. l'Arithmétique de Simon Stevin de Bruges, annotated by Albert Girard, Leyde 1625, p. 622.L. E. Dickson, History of the Theory of Numbers, Vol. II, Ch. VI, p. 227. "A. Girard ... had already made a determination of the numbers expressible as a sum of two integral squares: every square, every prime 4n+1, a product formed of such numbers, and the double of the foregoing" The statement that every prime p of the form is the sum of two squares is sometimes called Girard's theorem.L. E. Dickson, History of the Theory of Numbers, Vol. II, Ch. VI, p. 228. For his part, Fermat wrote an elaborate version of the statement (in which he also gave the number of possible expressions of the powers of p as a sum of two squares) in a letter to Marin Mersenne dated December 25, 1640: for this reason this version of the theorem is sometimes called Fermat's Christmas theorem.
Gaussian primes Fermat's theorem on sums of two squares is strongly related with the theory of Gaussian primes.
A Gaussian integer is a complex number such that and are integers. The norm of a Gaussian integer is an integer equal to the square of the absolute value of the Gaussian integer. The norm of a product of Gaussian integers is the product of their norms. This is the Diophantus identity, which results immediately from the similar property of the absolute value.
Gaussian integers form a principal ideal domain. This implies that Gaussian primes can be defined similarly as primes numbers, that is as those Gaussian integers that are not the product of two non-units (here the units are and ).
The multiplicative property of the norm implies that a prime number is either a Gaussian prime or the norm of a Gaussian prime. Fermat's theorem asserts that the first case occurs when and that the second case occurs when and The last case is not considered in Fermat's statement, but is trivial, as
Related results The above point of view on Fermat's theorem is a special case of the theory of factorization of ideals in rings of quadratic integers. In summary, if is the ring of algebraic integers in the quadratic field, then an odd prime number , not dividing , is either a prime element in or the ideal norm of an ideal of which is necessarily prime. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If is a principal ideal domain, then is an ideal norm if and only
with and both integers.
In a letter to Blaise Pascal dated September 25, 1654 Fermat announced the following two results that are essentially the special cases and If is an odd prime, then
Fermat wrote also: If two primes which end in 3 or 7 and surpass by 3 a multiple of 4 are multiplied, then their product will be composed of a square and the quintuple of another square. In other words, if are of the form or , then . Euler later extended this to the conjecture that
Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange. This more complicated formulation relies on the fact that is not a principal ideal domain, unlike and
Algorithm In 1990, Stan Wagon described a Las Vegas algorithm with a probabilistically polynomial complexity based on work by Serret and Hermite (1848), and Cornacchia (1908).. The probabilistic part consists in finding a quadratic non-residue, which can be done with success probability and then iterated if not successful. Conditionally this can also be done in deterministic polynomial time if the generalized Riemann hypothesis holds as explained for the Tonelli–Shanks algorithm.
Description Given an odd prime in the form , first find such that . This can be done by finding a quadratic non-residue modulo , say , and letting .
Such an will satisfy the condition since quadratic non-residues satisfy .
Once is determined, one can apply the Euclidean algorithm with and . Denote the first two remainders that are less than the square root of as and . Then it will be the case that .
In the Euclidean algorithm, we have a sequence of remainders that end with the greatest common divisor .
We compute these recursively with initial values :</p>
We can define another sequence by the same recurrence, but with initial values , :</p>
It turns out that the sequence is just the reverse of the sequence , up to signs.</p>
Moreover, one can see using the recurrence that for all . Square this equation and use to get . From there we just need to find the and that are the right size so that .
Example Take . A possible quadratic non-residue for 97 is 13, since . so we let . The Euclidean algorithm applied to 97 and 22 yields:
The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have , as expected.
Proofs Fermat usually did not write down proofs of his claims, and he did not provide a proof of this statement. The first proof was found by Euler after much effort and is based on infinite descent. He announced it in two letters to Goldbach, on May 6, 1747 and on April 12, 1749; he published the detailed proof in two articles (between 1752 and 1755).De numeris qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40)Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3-13) Lagrange gave a proof in 1775 that was based on his study of quadratic forms. This proof was simplified by Gauss in his Disquisitiones Arithmeticae (art. 182). Dedekind gave at least two proofs based on the arithmetic of the Gaussian integers. There is an elegant proof using Minkowski's theorem about convex sets. Simplifying an earlier short proof due to Heath-Brown (who was inspired by Liouville's idea), Zagier presented a non-constructive one-sentence proof in 1990.. And more recently Christopher gave a partition-theoretic proof.A. David Christopher. "A partition-theoretic proof of Fermat's Two Squares Theorem", Discrete Mathematics 339:4:1410–1411 (6 April 2016)
Euler's proof by infinite descent Euler succeeded in proving Fermat's theorem on sums of two squares in 1749, when he was forty-two years old. He communicated this in a letter to Goldbach dated 12 April 1749.Euler à Goldbach, lettre CXXV The proof relies on infinite descent, and is only briefly sketched in the letter. The full proof consists in five steps and is published in two papers. The first four steps are Propositions 1 to 4 of the first paperDe numeris qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40) and do not correspond exactly to the four steps below. The fifth step below is from the second paper.Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3-13) The summary is based on Edwards book, pages 45-48.
For the avoidance of ambiguity, zero will always be a valid possible constituent of "sums of two squares", so for example every square of an integer is trivially expressible as the sum of two squares by setting one of them to be zero.
1. The product of two numbers, each of which is a sum of two squares, is itself a sum of two squares. This is a well-known property, based on the identity
due to Diophantus.
2. If a number which is a sum of two squares is divisible by a prime which is a sum of two squares, then the quotient is a sum of two squares. (This is Euler's first Proposition).
Indeed, suppose for example that is divisible by and that this latter is a prime. Then divides
Since is a prime, it divides one of the two factors. Suppose that it divides . Since
(Diophantus's identity) it follows that must divide . So the equation can be divided by the square of . Dividing the expression by yields:
and thus expresses the quotient as a sum of two squares, as claimed.
On the other hand if divides , a similar argument holds by using the following variant of Diophantus's identity:
3. If a number which can be written as a sum of two squares is divisible by a number which is not a sum of two squares, then the quotient has a factor which is not a sum of two squares. (This is Euler's second Proposition). Suppose is a number not expressible as a sum of two squares, which divides . Write the quotient, factored into its (possibly repeated) prime factors, as so that . If all factors can be written as sums of two squares, then we can divide successively by , , etc., and applying step (2.) above we deduce that each successive, smaller, quotient is a sum of two squares. If we get all the way down to then itself would have to be equal to the sum of two squares, which is a contradiction. So at least one of the primes is not the sum of two squares.
4. If and are relatively prime positive integers then every factor of is a sum of two squares. (This is the step that uses step (3.) to produce an 'infinite descent' and was Euler's Proposition 4. The proof sketched below also includes the proof of his Proposition 3).
Let be relatively prime positive integers: without loss of generality is not itself prime, otherwise there is nothing to prove. Let therefore be a proper factor of , not necessarily prime: we wish to show that is a sum of two squares. Again, we lose nothing by assuming since the case is obvious.
Let be non-negative integers such that are the closest multiples of (in absolute value) to respectively. Notice that the differences and are integers of absolute value strictly less than : indeed, when is even, gcd; otherwise since gcd, we would also have gcd.
Multiplying out we obtain
uniquely defining a non-negative integer . Since divides both ends of this equation sequence it follows that must also be divisible by : say . Let be the gcd of and which by the co-primeness of is relatively prime to . Thus divides , so writing , and , we obtain the expression for relatively prime and , and with , since