Fermat's theorem on sums of two squares
Albert Girard was the first to make the observation, describing all positive integer numbers (not necessarily primes) expressible as the sum of two squares of positive integers; this was published in 1625. The statement that every prime "p" of the form "4n+1" is the sum of two squares is sometimes called "Girard's theorem". 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. A Gaussian integer is a complex number formula_4 such that and are integers. The "norm" formula_5 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 norm. This is 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 formula_6 and that the second case occurs when formula_7 and formula_8 The last case is not considered in Fermat's statement, but is trivial, as formula_9 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 formula_10 is the ring of algebraic integers in the quadratic field, then an odd prime number , not dividing , is either a prime element in formula_11 or the ideal norm of an ideal of formula_11 which is necessarily prime. Moreover, the law of quadratic reciprocity allows distinguishing the two cases in terms of congruences. If formula_10 is a principal ideal domain, then is an ideal norm if and only 
formula_14
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 formula_15 and formula_16 If is an odd prime, then
formula_17
formula_18
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
formula_19
formula_20
Both Fermat's assertion and Euler's conjecture were established by Joseph-Louis Lagrange. This more complicate formulation relies on the fact that formula_21 is not a principal ideal domain, contrarily to formula_22 and formula_23 There is a trivial algorithm for decomposing a prime of the form formula_7 into a sum of two squares: For all such formula_25, test whether the square root of formula_26 is an integer. If this the case, one has got the decomposition. However the input size of the algorithm is formula_27 the number of digits of (up to a constant factor that depends on the numeral base). The number of needed tests is of the order of formula_28 and thus exponential in the input size. So the computational complexity of this algorithm is exponential. An algorithm with a polynomial complexity has been described by
Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908). Given an odd prime formula_29 in the form formula_30, first find formula_31 such that formula_32.
This can be done by finding a Quadratic non-residue modulo formula_29, say formula_34, and letting
formula_35. Such an formula_31 will satisfy the condition since quadratic non-residues satisfy formula_37. Once formula_31 is determined, one can apply the Euclidean algorithm with formula_29 and formula_31. Denote the first two remainders that are less than the square root of formula_29 as formula_42 and formula_43. Then it will be the case that formula_44. Take formula_45. A possible quadratic non-residue for 97 is 13, since formula_46. so we let formula_47. The Euclidean algorithm applied to 97 and 22 yields:
formula_48
formula_49
formula_50
formula_51
The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have formula_52, as expected. 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). 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. 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. 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 paper and do not correspond exactly to the four steps below. The fifth step below is from the second paper. 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
formula_53
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 formula_54 is divisible by formula_55 and that this latter is a prime. Then formula_56 divides
formula_57
Since formula_55 is a prime, it divides one of the two factors. Suppose that it divides formula_59. Since
formula_53
(Diophantus's identity) it follows that formula_55 must divide formula_62. So the equation can be divided by the square of formula_55. Dividing the expression by formula_64 yields:
formula_65
and thus expresses the quotient as a sum of two squares, as claimed. On the other hand if formula_55 divides formula_67, a similar argument holds by using the following variant of Diophantus's identity:
formula_68
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 formula_34 is a number not expressible as a sum of two squares, which divides formula_70. Write the quotient, factored into its (possibly repeated) prime factors, as formula_71 so that formula_72. If all factors formula_73 can be written as sums of two squares, then we can divide formula_70 successively by formula_75, formula_76, 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 formula_34 then formula_34 itself would have to be equal to the sum of two squares, which is a contradiction. So at least one of the primes formula_73 is not the sum of two squares. 4. "If formula_42 and formula_43 are relatively prime positive integers then every factor of formula_54 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 formula_83 be relatively prime positive integers: without loss of generality formula_70 is not itself prime, otherwise there is nothing to prove. Let formula_34 therefore be a "proper" factor of formula_70, not necessarily prime: we wish to show that formula_34 is a sum of two squares. Again, we lose nothing by assuming formula_88 since the case formula_89 is obvious. Let formula_90 be non-negative integers such that formula_91 are the closest multiples of formula_34 (in absolute value) to formula_83 respectively. Notice that the differences formula_94 and formula_95 are integers of absolute value strictly less than formula_96: indeed, when formula_88 is even, gcdformula_98; otherwise since gcdformula_99, we would also have gcdformula_100. Multiplying out we obtain
formula_101
uniquely defining a non-negative integer formula_102. Since formula_34 divides both ends of this equation sequence it follows that formula_104 must also be divisible by formula_34: say formula_106. Let formula_107 be the gcd of formula_108 and formula_109 which by the co-primeness of formula_83 is relatively prime to formula_34. Thus formula_112 divides formula_113, so writing formula_114, formula_115 and formula_116, we obtain the expression formula_117 for relatively prime formula_118 and formula_119, and with formula_120, since
formula_121
Now finally, the "descent" step: if formula_34 is not the sum of two squares, then by step (3.) there must be a factor formula_123 say of formula_124 which is not the sum of two squares. But formula_125 and so repeating these steps (initially with formula_126 in place of formula_127, and so on "ad infinitum") we shall be able to find a strictly decreasing infinite sequence formula_128 of positive integers which are not themselves the sums of two squares but which divide into a sum of two relatively prime squares. Since such an infinite descent is impossible, we conclude that formula_34 must be expressible as a sum of two squares, as claimed. 5. "Every prime of the form formula_130 is a sum of two squares. "
(This is the main result of Euler's second paper). If formula_131, then by Fermat's Little Theorem each of the numbers formula_132 is congruent to one modulo formula_29. The differences formula_134 are therefore all divisible by formula_29. Each of these differences can be factored as
formula_136
Since formula_29 is prime, it must divide one of the two factors. If in any of the formula_138 cases it divides the first factor, then by the previous step we conclude that formula_29 is itself a sum of two squares (since formula_42 and formula_43 differ by formula_142, they are relatively prime). So it is enough to show that formula_29 cannot always divide the second factor. If it divides all formula_138 differences formula_145, then it would divide all formula_146 differences of successive terms, all formula_147 differences of the differences, and so forth. Since the formula_148th differences of the sequence formula_149 are all equal to formula_150 (Finite difference), the formula_151th differences would all be constant and equal to formula_152, which is certainly not divisible by formula_29. Therefore, formula_29 cannot divide all the second factors which proves that formula_29 is indeed the sum of two squares. Lagrange completed a proof in 1775 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. An (integral binary) quadratic form is an expression of the form formula_156 with formula_157 integers. A number formula_158 is said to be "represented by the form" if there exist integers formula_159 such that formula_160. Fermat's theorem on sums of two squares is then equivalent to the statement that a prime formula_29 is represented by the form formula_162 (i.e., formula_163, formula_164) exactly when formula_29 is congruent to formula_142 modulo formula_167. The discriminant of the quadratic form is defined to be formula_168. The discriminant of formula_162 is then equal to formula_170. Two forms formula_171 and formula_172 are "equivalent" if and only if there exist substitutions with integer coefficients
 formula_173
 formula_174
with formula_175 such that, when substituted into the first form, yield the second. Equivalent forms are readily seen to have the same discriminant, and hence also the same parity for the middle coefficient formula_176, which coincides with the parity of the discriminant. Moreover, it is clear that equivalent forms will represent exactly the same integers, because these kind of substitutions can be reversed by substitutions of the same kind. 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 formula_29. For example, one can use a form
formula_178
where the first coefficient "a" = formula_29 was chosen so that the form represents formula_29 by setting "x" = 1, and "y" = 0, the coefficient "b" = 2"m" is an arbitrary even number (as it must be, to get an even discriminant), and finally formula_181 is chosen so that the discriminant formula_182 is equal to −4, which guarantees that the form is indeed equivalent to formula_183. Of course, the coefficient formula_181 must be an integer, so the problem is reduced to finding some integer "m" such that formula_29 divides formula_186: or in other words, a " 'square root of -1 modulo formula_29' ". We claim such a square root of formula_188 is given by formula_189. Firstly it follows from Euclid's Fundamental Theorem of Arithmetic that formula_190. Consequently, formula_191: that is, formula_192 are their own inverses modulo formula_29 and this property is unique to them. It then follows from the validity of Euclidean division in the integers, and the fact that formula_29 is prime, that for every formula_195 the gcd of formula_42 and formula_29 may be expressed via the Euclidean algorithm yielding a unique and "distinct" inverse formula_198 of formula_42 modulo formula_29. In particular therefore the product of "all" non-zero residues modulo formula_29 is formula_188. Let formula_203: from what has just been observed, formula_204. But by definition, since each term in formula_205 may be paired with its negative in formula_206, formula_207, which since formula_29 is odd shows that formula_209, as required. 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. One appears in section 27 of his exposition of ideals published in 1877; the second appeared in Supplement XI to Peter Gustav Lejeune Dirichlet's "Vorlesungen über Zahlentheorie", and was published in 1894. 1. First proof. If formula_29 is an odd prime number, then we have formula_211 in the Gaussian integers. Consequently, writing a Gaussian integer ω = "x" + "iy" with "x,y" ∈ Z and applying the Frobenius automorphism in Z["i"]/("p"), one finds
formula_212
since the automorphism fixes the elements of Z/("p"). In the current case, formula_131 for some integer n, and so in the above expression for ωp, the exponent (p-1)/2 of -1 is even. Hence the right hand side equals ω, so in this case the Frobenius endomorphism of Z["i"]/("p") is the identity. Kummer had already established that if } is the order of the Frobenius automorphism of Z["i"]/("p"), then the ideal formula_214 in Z["i"] would be a product of 2/"f" distinct prime ideals. (In fact, Kummer had established a much more general result for any extension of Z obtained by adjoining a primitive "m"-th root of unity, where "m" was any positive integer; this is the case of that result.) Therefore, the ideal ("p") is the product of two different prime ideals in Z["i"]. Since the Gaussian integers are a Euclidean domain for the norm function formula_215, every ideal is principal and generated by a nonzero element of the ideal of minimal norm. Since the norm is multiplicative, the norm of a generator formula_216 of one of the ideal factors of ("p") must be a strict divisor of formula_217, so that we must have formula_218, which gives Fermat's theorem. 2. Second proof. This proof builds on Lagrange's result that if formula_131 is a prime number, then there must be an integer "m" such that formula_220 is divisible by "p" (we can also see this by Euler's criterion); it also uses the fact that the Gaussian integers are a unique factorization domain (because they are a Euclidean domain). Since does not divide either of the Gaussian integers formula_221 and formula_222 (as it does not divide their imaginary parts), but it does divide their product formula_220, it follows that formula_29 cannot be a prime element in the Gaussian integers. We must therefore have a nontrivial factorization of "p" in the Gaussian integers, which in view of the norm can have only two factors (since the norm is multiplicative, and formula_225, there can only be up to two factors of p), so it must be of the form formula_226 for some integers formula_31 and formula_228. This immediately yields that formula_229. For formula_29 congruent to formula_142 mod formula_167 a prime, formula_188 is a quadratic residue mod formula_29 by Euler's criterion. Therefore, there exists an integer formula_235 such that formula_29 divides formula_186. Let formula_238 be the standard basis elements for the vector space formula_239 and set formula_240 and formula_241. Consider the lattice formula_242. If formula_243 then formula_244. Thus formula_29 divides formula_246 for any formula_247. The area of the fundamental parallelogram of the lattice is formula_29. The area of the open disk, formula_249, of radius formula_250 centered around the origin is formula_251. Furthermore, formula_249 is convex and symmetrical about the origin. Therefore, by Minkowski's theorem there exists a nonzero vector formula_247 such that formula_254. Both formula_255 and formula_256 so formula_257. Hence formula_29 is the sum of the squares of the components of formula_259. Let formula_7 be prime, let formula_261 denote the natural numbers (with or without zero), and consider the finite set formula_262 of triples of numbers. Then formula_263 has two involutions: an obvious one formula_264 whose fixed points formula_265 correspond to representations of formula_29 as a sum of two squares, and a more complicated one,
 formula_267
which has exactly one fixed point formula_268. Two involutions over the same finite set must have sets of fixed points with the same parity, and since the second involution has an odd number of fixed points, so does the first. Zero is even, so the first involution has a nonzero number of fixed points, any one of which gives a representation of formula_29 as a sum of two squares. This proof, due to Zagier, is a simplification of an earlier proof by Heath-Brown, which in turn was inspired by a proof of Liouville. 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. This proof is equivalent to a geometric or "visual" proof using "windmill" figures, given by Alexander Spivak in 2006 and described in this MathOverflow post and this Mathologer YouTube video . In 2016, A. David Christopher gave a partition-theoretic proof by considering partitions of the odd prime formula_158 having exactly two sizes formula_271, each occurring exactly formula_272 times, and by showing that at least one such partition exists if formula_158 is congruent to 1 modulo 4.
Proofs ; Lagrange's proof through quadratic forms
This is the easier part of the theorem, and follows immediately from the observation that all squares are congruent to 0 or 1 modulo 4.