1000/1000
Hot
Most Recent
Fermat's theorem on sums of two squares asserts that an odd prime number p can be expressed as with integer x and y if and only if p is congruent to 1 (mod 4). The statement was announced by Girard in 1625, and again by Fermat in 1640, but neither supplied a proof. The "only if" clause is easy: a perfect square is congruent to 0 or 1 modulo 4, hence a sum of two squares is congruent to 0, 1, or 2. An odd prime number is congruent to either 1 or 3 modulo 4, and the second possibility has just been ruled out. The first proof that such a representation exists was given by Leonhard Euler in 1747 and was complicated. Since then, many different proofs have been found. Among them, the proof using Minkowski's theorem about convex sets and Don Zagier's short proof based on involutions have appeared.
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.^{[1]} 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^{[2]} and do not correspond exactly to the four steps below. The fifth step below is from the second paper.^{[3]}^{[4]}
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.
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).
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).
4. If [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are relatively prime positive integers then every factor of [math]\displaystyle{ a^2 + b^2 }[/math] 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).
5. Every prime of the form [math]\displaystyle{ 4n+1 }[/math] is a sum of two squares. (This is the main result of Euler's second paper).
Lagrange completed a proof in 1775^{[5]} 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 [math]\displaystyle{ ax^2 + bxy + cy^2 }[/math] with [math]\displaystyle{ a,b,c }[/math] integers. A number [math]\displaystyle{ n }[/math] is said to be represented by the form if there exist integers [math]\displaystyle{ x,y }[/math] such that [math]\displaystyle{ n = ax^2 + bxy + cy^2 }[/math]. Fermat's theorem on sums of two squares is then equivalent to the statement that a prime [math]\displaystyle{ p }[/math] is represented by the form [math]\displaystyle{ x^2 + y^2 }[/math] (i.e., [math]\displaystyle{ a=c=1 }[/math], [math]\displaystyle{ b=0 }[/math]) exactly when [math]\displaystyle{ p }[/math] is congruent to [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ 4 }[/math].
The discriminant of the quadratic form is defined to be [math]\displaystyle{ b^2 - 4ac }[/math]. The discriminant of [math]\displaystyle{ x^2 + y^2 }[/math] is then equal to [math]\displaystyle{ -4 }[/math].
Two forms [math]\displaystyle{ ax^2 + bxy + cy^2 }[/math] and [math]\displaystyle{ a'x'^2 + b'x'y' + c'y'^2 }[/math] are equivalent if and only if there exist substitutions with integer coefficients
with [math]\displaystyle{ \alpha\delta - \beta\gamma = \pm 1 }[/math] 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 [math]\displaystyle{ b }[/math], 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 [math]\displaystyle{ p }[/math]. For example, one can use a form
where the first coefficient a = [math]\displaystyle{ p }[/math] was chosen so that the form represents [math]\displaystyle{ p }[/math] by setting x = 1, and y = 0, the coefficient b = 2m is an arbitrary even number (as it must be, to get an even discriminant), and finally [math]\displaystyle{ c=\frac{m^2+1}{p} }[/math] is chosen so that the discriminant [math]\displaystyle{ b^2-4ac=4m^2-4pc }[/math] is equal to −4, which guarantees that the form is indeed equivalent to [math]\displaystyle{ x^2+y^2 }[/math]. Of course, the coefficient [math]\displaystyle{ c=\frac{m^2+1}{p} }[/math] must be an integer, so the problem is reduced to finding some integer m such that [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ m^2+1 }[/math]: or in other words, a 'square root of -1 modulo [math]\displaystyle{ p }[/math]' .
We claim such a square root of [math]\displaystyle{ -1 }[/math] is given by [math]\displaystyle{ K = \prod_{k=1}^\frac{p-1}{2} k }[/math]. Firstly it follows from Euclid's Fundamental Theorem of Arithmetic that [math]\displaystyle{ ab \equiv 0 \pmod p \iff a \equiv 0 \pmod p \ \ \hbox{or}\ \ b \equiv 0 \pmod p }[/math]. Consequently [math]\displaystyle{ a^2 \equiv 1 \pmod p \iff a \equiv \pm 1 \pmod p }[/math]: that is, [math]\displaystyle{ \pm 1 }[/math] are their own inverses modulo [math]\displaystyle{ p }[/math] and this property is unique to them. It then follows from the validity of Euclidean division in the integers, and the fact that [math]\displaystyle{ p }[/math] is prime, that for every [math]\displaystyle{ 2 \leq a \leq p-2 }[/math] the gcd of [math]\displaystyle{ a }[/math] and [math]\displaystyle{ p }[/math] may be expressed via the Euclidean algorithm yielding a unique and distinct inverse [math]\displaystyle{ a^{-1} \neq a }[/math] of [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p }[/math]. In particular therefore the product of all non-zero residues modulo [math]\displaystyle{ p }[/math] is [math]\displaystyle{ -1 }[/math]. Let [math]\displaystyle{ L = \prod_{l=\frac{p+1}{2}}^{p-1} l }[/math]: from what has just been observed, [math]\displaystyle{ KL \equiv -1 \pmod p }[/math]. But by definition, since each term in [math]\displaystyle{ K }[/math] may be paired with its negative in [math]\displaystyle{ L }[/math], [math]\displaystyle{ L = (-1)^\frac{p-1}{2}K }[/math], which since [math]\displaystyle{ p }[/math] is odd shows that [math]\displaystyle{ K^2 \equiv -1 \pmod p \iff p \equiv 1 \pmod 4 }[/math], 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 [math]\displaystyle{ p }[/math] is an odd prime number, then we have [math]\displaystyle{ i^{p-1} = (-1)^{\frac{p-1}{2}} }[/math] 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
since the automorphism fixes the elements of Z/(p). In the current case, [math]\displaystyle{ p=4n+1 }[/math] 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 f ∈ {1,2} is the order of the Frobenius automorphism of Z[i]/(p), then the ideal [math]\displaystyle{ (p) }[/math] 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 m = 4 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 [math]\displaystyle{ N(x + iy)=x^2+y^2 }[/math], 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 [math]\displaystyle{ \alpha }[/math] of one of the ideal factors of (p) must be a strict divisor of [math]\displaystyle{ N(p) = p^2 }[/math], so that we must have [math]\displaystyle{ p = N(\alpha) = N(a+bi) = a^2 + b^2 }[/math], which gives Fermat's theorem.
2. Second proof. This proof builds on Lagrange's result that if [math]\displaystyle{ p=4n+1 }[/math] is a prime number, then there must be an integer m such that [math]\displaystyle{ m^2 + 1 }[/math] 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 p ∈ Z does not divide either of the Gaussian integers [math]\displaystyle{ m + i }[/math] and [math]\displaystyle{ m-i }[/math] (as it does not divide their imaginary parts), but it does divide their product [math]\displaystyle{ m^2 + 1 }[/math], it follows that [math]\displaystyle{ p }[/math] 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 [math]\displaystyle{ p^2 = N(p) }[/math], there can only be up to two factors of p), so it must be of the form [math]\displaystyle{ p = (x+yi)(x-yi) }[/math] for some integers [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math]. This immediately yields that [math]\displaystyle{ p = x^2 + y^2 }[/math].
For [math]\displaystyle{ p }[/math] congruent to [math]\displaystyle{ 1 }[/math] mod [math]\displaystyle{ 4 }[/math] a prime, [math]\displaystyle{ -1 }[/math] is a quadratic residue mod [math]\displaystyle{ p }[/math] by Euler's criterion. Therefore, there exists an integer [math]\displaystyle{ m }[/math] such that [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ m^2+1 }[/math]. Let [math]\displaystyle{ \hat{i}, \hat{j} }[/math] be the standard basis elements for the vector space [math]\displaystyle{ \mathbb{R}^2 }[/math] and set [math]\displaystyle{ \vec{u} = \hat{i} + m\hat{j} }[/math] and [math]\displaystyle{ \vec{v} = 0\hat{i} + p\hat{j} }[/math]. Consider the lattice [math]\displaystyle{ S = \{a\vec{u} + b\vec{v} \mid a, b \in \mathbb Z\} }[/math]. If [math]\displaystyle{ \vec{w} = a\vec{u} + b\vec{v} = a \hat{i} + (am + bp)\hat{j} \in S }[/math] then [math]\displaystyle{ \|\vec{w}\|^2 \equiv a^2 + (am+bp)^2 \equiv a^2(1 + m^2) \equiv 0\pmod{p} }[/math]. Thus [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ \|\vec{w}\|^2 }[/math] for any [math]\displaystyle{ \vec{w} \in S }[/math].
The area of the fundamental parallelogram of the lattice is [math]\displaystyle{ p }[/math]. The area of the open disk, [math]\displaystyle{ D }[/math], of radius [math]\displaystyle{ \sqrt{2p} }[/math] centered around the origin is [math]\displaystyle{ 2 \pi p \gt 4p }[/math]. Furthermore, [math]\displaystyle{ D }[/math] is convex and symmetrical about the origin. Therefore, by Minkowski's theorem there exists a nonzero vector [math]\displaystyle{ \vec{w} \in S }[/math] such that [math]\displaystyle{ \vec{w} \in D }[/math]. Both [math]\displaystyle{ \|\vec{w}\|^2 \lt 2p }[/math] and [math]\displaystyle{ p \mid \|\vec{w}\|^2 }[/math] so [math]\displaystyle{ p = \|\vec{w}\|^2 }[/math]. Hence [math]\displaystyle{ p }[/math] is the sum of the squares of the components of [math]\displaystyle{ \vec{w} }[/math].
Let [math]\displaystyle{ p=4k+1 }[/math] be prime, let [math]\displaystyle{ \mathbb{N} }[/math] denote the natural numbers (with or without zero), and consider the finite set [math]\displaystyle{ S=\{(x,y,z)\in\mathbb{N}^3: x^2+4yz=p\} }[/math] of triples of numbers. Then [math]\displaystyle{ S }[/math] has two involutions: an obvious one [math]\displaystyle{ (x,y,z)\mapsto (x,z,y) }[/math] whose fixed points [math]\displaystyle{ (x,y,y) }[/math] correspond to representations of [math]\displaystyle{ p }[/math] as a sum of two squares, and a more complicated one,
which has exactly one fixed point [math]\displaystyle{ (1,1,k) }[/math]. 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 [math]\displaystyle{ p }[/math] 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.
In 2016, A. David Christopher gave a partition-theoretic proof by considering partitions of the odd prime [math]\displaystyle{ n }[/math] having exactly two sizes [math]\displaystyle{ a_i (i=1,2) }[/math], each occurring exactly [math]\displaystyle{ a_i }[/math] times, and by showing that at least one such partition exists if [math]\displaystyle{ n }[/math] is congruent to 1 modulo 4.^{[6]}