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.
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.
[4] 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.
Fermat's theorem on sums of two squares is strongly related with the theory of Gaussian primes.
This is the Diophantus identity, which results immediately from the similar property of the absolute value.
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.
Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences.
In a letter to Blaise Pascal dated September 25, 1654 Fermat announced the following two results that are essentially the special cases
If p is an odd prime, then Fermat wrote also: In other words, if p, q are of the form 20k + 3 or 20k + 7, then pq = x2 + 5y2.
the number of digits of p (up to a constant factor that depends on the numeral base).
A Las Vegas algorithm with a probabilistically polynomial complexity has been described by Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908).
[5] The probabilistic part consists in finding a quadratic non-residue, which can be done with success probability
Conditionally this can also be done in deterministic polynomial time if the generalized Riemann hypothesis holds as explained for the Tonelli–Shanks algorithm.
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).
[7][8] Lagrange gave a proof in 1775 that was based on his study of quadratic forms.
Dedekind gave at least two proofs based on the arithmetic of the Gaussian integers.
[10] Euler succeeded in proving Fermat's theorem on sums of two squares in 1749, when he was forty-two years old.
[11] The proof relies on infinite descent, and is only briefly sketched in the letter.
Lagrange completed a proof in 1775[15] based on his general theory of integral quadratic forms.
The following presentation incorporates a slight simplification of his argument, due to Gauss, which appears in article 182 of the Disquisitiones Arithmeticae.
Fermat's theorem on sums of two squares is then equivalent to the statement that a prime
Equivalent forms are readily seen to have the same discriminant, and hence also the same parity for the middle coefficient
Lagrange proved that all positive definite forms of discriminant −4 are equivalent.
Thus, to prove Fermat's theorem it is enough to find any positive definite form of discriminant −4 that represents
may be expressed via the Euclidean algorithm yielding a unique and distinct inverse
Richard Dedekind gave at least two proofs of Fermat's theorem on sums of two squares, both using the arithmetical properties of the Gaussian integers, which are numbers of the form a + bi, where a and b are integers, and i is the square root of −1.
Hence the right hand side equals ω, so in this case the Frobenius endomorphism of Z[i]/(p) is the identity.
The technique of the proof is a combinatorial analogue of the topological principle that the Euler characteristics of a topological space with an involution and of its fixed-point set have the same parity and is reminiscent of the use of sign-reversing involutions in the proofs of combinatorial bijections.
In 2016, A. David Christopher gave a partition-theoretic proof by considering partitions of the odd prime