View source for Fermat's theorem on sums of two squares

{{short description|Condition under which an odd prime is a sum of two squares}}
{{For|other theorems named after Pierre de Fermat|Fermat's theorem}}
In [[additive number theory]], '''[[Pierre de Fermat|Fermat]]'s theorem on sums of two squares''' states that an [[Even and odd numbers|odd]] [[prime number|prime]] ''p'' can be expressed as:

:<math>p = x^2 + y^2,</math>

with ''x'' and ''y'' integers, [[if and only if]]

:<math>p \equiv 1 \pmod{4}.</math>

The prime numbers for which this is true are called [[Pythagorean prime]]s.
For example, the primes 5, 13, 17, 29, 37 and 41 are all [[Modular_arithmetic#Congruence|congruent]] to 1 [[modular arithmetic|modulo]] 4, and they can be expressed as sums of two squares in the following ways:

:<math>5 = 1^2 + 2^2, \quad 13 = 2^2 + 3^2, \quad 17 = 1^2 + 4^2, \quad 29 = 2^2 + 5^2, \quad 37 = 1^2 + 6^2, \quad 41 = 4^2 + 5^2.</math>

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 [[Brahmagupta–Fibonacci identity|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.<ref>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.</ref> 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.<ref>[[Simon Stevin]]. [https://archive.org/stream/larithmetiqvedes00stev#page/622/mode/2up ''l'Arithmétique de Simon Stevin de Bruges'', annotated by Albert Girard, Leyde 1625, p. 622].</ref><ref>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"</ref> The statement that every prime ''p'' of the form ''4n+1'' is the sum of two squares is sometimes called ''Girard's theorem''.<ref>L. E. Dickson, History of the Theory of Numbers, Vol. II,  Ch. VI, p. 228.</ref> 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 prime]]s.

A [[Gaussian integer]] is a [[complex number]] <math>a+ib</math> such that {{mvar|a}} and {{mvar|b}} are integers. The ''norm'' <math>N(a+ib)=a^2+b^2</math> 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 [[Brahmagupta–Fibonacci identity|Diophantus identity]], which results immediately from the similar property of the absolute value.

Gaussian integers form a [[principal ideal domain]]. This implies that [[Gaussian prime]]s can be defined similarly as primes numbers, that is as those Gaussian integers that are not the product of two [[unit (ring theory)|non-units]] (here the units are {{math|1, −1, ''i''}} and {{math|−''i''}}). 

The multiplicative property of the norm implies that a prime number {{mvar|p}} is either a Gaussian prime or the norm of a Gaussian prime. Fermat's theorem asserts that the first case occurs when <math>p=4k+3,</math> and that the second case occurs when <math>p=4k+1</math> and <math>p=2.</math> The last case is not considered in Fermat's statement, but is trivial, as <math>2 = 1^2+1^2 =N(1+i).</math>

==Related results==
The above point of view on Fermat's theorem is a special case of the theory of [[Quadratic field#Prime factorization into ideals|factorization of ideals in rings of quadratic integers]]. In summary, if <math>\mathcal O_\sqrt{d}</math> is the ring of [[algebraic integer]]s in the [[quadratic field]], then an odd prime number {{mvar|p}}, not dividing {{mvar|d}}, is either a [[prime element]] in <math>\mathcal O_\sqrt{d},</math> or the [[ideal norm]] of an ideal of <math>\mathcal O_\sqrt{d},</math> which is necessarily prime. Moreover, the [[law of quadratic reciprocity]] allows distinguishing the two cases in terms of congruences. If <math>\mathcal O_\sqrt{d}</math> is a [[principal ideal domain]], then {{mvar|p}} is an ideal norm if and only 
:<math>4p=a^2-db^2,</math>
with {{mvar|a}} and {{mvar|b}} both integers.

In a letter to [[Blaise Pascal]] dated September 25,  1654 Fermat announced the following two results that are essentially the special cases <math>d=-2</math> and <math>d=-3.</math> If {{mvar|p}} is an odd prime, then
:<math>p = x^2 + 2y^2 \iff p\equiv 1\mbox{ or }p\equiv 3\pmod{8},</math>
:<math>p= x^2 + 3y^2 \iff p\equiv 1 \pmod{3}.</math>

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 {{math|''p, q''}} are of the form {{math|20''k'' + 3}} or {{math|20''k'' + 7}}, then {{math|1=''pq'' = ''x''<sup>2</sup> + 5''y''<sup>2</sup>}}. Euler later extended this to the conjecture that
:<math>p = x^2 + 5y^2 \iff p\equiv 1\mbox{ or }p\equiv 9\pmod{20},</math>
:<math>2p = x^2 + 5y^2 \iff p\equiv 3\mbox{ or }p\equiv 7\pmod{20}.</math>

Both Fermat's assertion and Euler's conjecture were established by [[Joseph-Louis Lagrange]]. This more complicated formulation relies on the fact that <math>\mathcal O_\sqrt{-5}</math> is not a principal ideal domain, unlike <math>\mathcal O_\sqrt{-2}</math> and <math>\mathcal O_\sqrt{-3}.</math>

==Algorithm==
There is a trivial [[algorithm]] for decomposing a prime of the form <math>p=4k+1</math> into a sum of two squares: For all {{mvar|n}} such <math>1\le n<\sqrt p </math>, test whether the square root of <math>p-n^2</math> is an integer. If this is the case, one has got the decomposition.

However the input size of the algorithm is <math>\log p,</math> the number of digits of {{mvar|p}} (up to a constant factor that depends on the [[numeral base]]). The number of needed tests is of the order of <math>\sqrt p = \exp \left (\frac {\log p}2\right),</math> and thus [[exponential function|exponential]] in the input size. So the [[computational complexity]] of this algorithm is [[exponential time|exponential]].

A [[Las Vegas algorithm]] with a [[Probabilistic_Turing_machine|probabilistically]] [[polynomial complexity]] has been described by
Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908).<ref>{{citation
 | last = Wagon | first = Stan  | authorlink = 
 | doi = 10.2307/2323912
 | issue = 2
 | journal = [[American Mathematical Monthly]]
 | mr = 1041889
 | page = 125
 | title = Editor's Corner: The Euclidean Algorithm Strikes Again
 | volume = 97
 | year = 1990}}.</ref>
The probabilistic part consists in finding a quadratic non-residue, which can be done with success probability <math>\approx\frac{1}{2}</math> 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#Speed_of_the_algorithm|Tonelli–Shanks algorithm]].

=== Description ===
Given an odd prime <math>p</math> in the form <math>4k+1</math>, first find <math>x</math> such that <math>x^2\equiv-1 \pmod{p}</math>.
This can be done by finding a [[quadratic non-residue]] modulo <math>p</math>, say <math>q</math>, and letting
<math>x=q^\frac{p-1}{4} \pmod{p}</math>. 

Such an <math>x</math> will satisfy the condition since quadratic non-residues satisfy <math>q^\frac{p-1}{2}\equiv -1 \pmod{p}</math>.

Once <math>x</math> is determined, one can apply the [[Euclidean algorithm]] with <math>p</math> and <math>x</math>. Denote the first two remainders that are less than the square root of <math>p</math> as <math>a</math> and <math>b</math>. Then it will be the case that <math>a^2+b^2=p</math>.

=== Example ===
Take <math>p = 97</math>. A possible quadratic non-residue for 97 is 13, since <math>13^\frac{97-1}{2}\equiv-1 \pmod{97}</math>. so we let <math>x=13^\frac{97-1}{4}=22 \pmod{97}</math>.
The Euclidean algorithm applied to 97 and 22 yields:
<math display="block">97 = 22(4) + 9, </math>
<math display="block">22 = 9(2) + 4,</math>
<math display="block">9 = 4(2) + 1,</math>
<math display="block">4 = 1(4).</math>
The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have <math>97 = 9^2 + 4^2</math>, 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 [[Christian Goldbach|Goldbach]], on May 6, 1747 and on April 12, 1749; he published the detailed proof in two articles (between 1752 and 1755).<ref>De numeris qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40)</ref><ref>Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3-13)</ref>  [[Joseph Louis Lagrange|Lagrange]] gave a proof in 1775 that was based on his study of [[quadratic forms]]. This proof was simplified by [[Carl Friedrich Gauss|Gauss]] in his ''[[Disquisitiones Arithmeticae]]'' (art. 182). [[Richard Dedekind|Dedekind]] gave at least two proofs based on the arithmetic of the [[Gaussian integer]]s. There is an elegant proof using [[Minkowski's theorem]] about convex sets. Simplifying an earlier short proof due to [[Roger Heath-Brown|Heath-Brown]] (who was inspired by [[Liouville]]'s idea), [[Don Zagier|Zagier]] presented a non-constructive one-sentence proof in 1990.<ref>{{citation
 | last = Zagier | first = D. | authorlink = Don Zagier
 | doi = 10.2307/2323918
 | issue = 2
 | journal = [[American Mathematical Monthly]]
 | mr = 1041893
 | page = 144
 | title = A one-sentence proof that every prime ''p''&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;4) is a sum of two squares
 | volume = 97
 | year = 1990}}.</ref>
And more recently Christopher gave a [[Partition (number theory)| partition-theoretic]] proof.<ref>A. David Christopher. "A partition-theoretic proof of Fermat's Two Squares Theorem", ''Discrete Mathematics'' '''339''':4:1410–1411 (6 April 2016) {{doi|10.1016/j.disc.2015.12.002}}</ref>

===Euler's proof by infinite descent===
[[Leonhard Euler|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 [[Christian Goldbach|Goldbach]] dated 12 April 1749.<ref>[http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0852.pdf Euler à Goldbach, lettre CXXV]</ref> The proof relies on [[proof by infinite descent|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<ref>De numeris qui sunt aggregata duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3-40) [http://www.math.dartmouth.edu/~euler/docs/originals/E228.pdf]</ref> and do not correspond exactly to the four steps below. The fifth step below is from the second paper.<ref>Demonstratio theorematis FERMATIANI omnem numerum primum formae 4n+1 esse summam duorum quadratorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3-13) [http://www.math.dartmouth.edu/~euler/docs/originals/E241.pdf]</ref><ref>The summary is based on Edwards book, pages 45-48.</ref>

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
:::<math>(a^2+b^2)(p^2+q^2) = (ap+bq)^2 + (aq-bp)^2</math>

::due to [[Brahmagupta–Fibonacci identity|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 <math>a^2 + b^2</math> is divisible by <math>p^2+q^2</math> and that this latter is a prime. Then <math>p^2 + q^2</math> divides
:::<math>(pb-aq)(pb+aq) = p^2b^2 - a^2q^2 = p^2(a^2+b^2) - a^2(p^2+q^2).</math>

::Since <math>p^2+q^2</math> is a prime, it divides one of the two factors. Suppose that it divides <math>pb-aq</math>. Since
:::<math>(a^2+b^2)(p^2+q^2) = (ap+bq)^2 + (aq-bp)^2</math>

::(Diophantus's identity) it follows that <math>p^2+q^2</math> must divide <math>(ap+bq)^2</math>. So the equation can be divided by the square of <math>p^2+q^2</math>. Dividing the expression by <math>(p^2+q^2)^2</math> yields:
:::<math>\frac{a^2+b^2}{p^2+q^2} = \left(\frac{ap+bq}{p^2+q^2}\right)^2 + \left(\frac{aq-bp}{p^2+q^2}\right)^2</math>

::and thus expresses the quotient as a sum of two squares, as claimed.

::On the other hand if <math>p^2+q^2</math> divides <math>pb+aq</math>, a similar argument holds by using the following variant of Diophantus's identity:
:::<math>(a^2+b^2)(q^2+p^2) = (aq+bp)^2 + (ap-bq)^2 . </math>

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 <math>q</math> is a number not expressible as a sum of two squares, which divides <math>a^2+b^2</math>. Write the quotient, factored into its (possibly repeated) prime factors, as <math>p_1p_2\cdots p_n</math> so that <math>a^2+b^2 = q p_1p_2\cdots p_n</math>. If all factors <math>p_i</math> can be written as sums of two squares, then we can divide <math>a^2+b^2</math> successively by <math>p_1</math>, <math>p_2</math>, 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 <math>q</math> then <math>q</math> itself would have to be equal to the sum of two squares, which is a contradiction. So at least one of the primes <math>p_i</math> is not the sum of two squares.

4. ''If <math>a</math> and <math>b</math> are relatively prime positive integers then every factor of <math>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).

::Let <math>a,b</math> be relatively prime positive integers: [[without loss of generality]] <math>a^2+b^2</math> is not itself prime, otherwise there is nothing to prove. Let <math>q</math> therefore be a ''proper'' factor of <math>a^2+b^2</math>, not necessarily prime: we wish to show that <math>q</math> is a sum of two squares. Again, we lose nothing by assuming <math> q > 2 </math> since the case <math> q = 2 = 1^2 + 1^2 </math> is obvious.

::Let <math>m,n</math> be non-negative integers such that <math>mq,nq</math> are the closest multiples of <math>q</math> (in absolute value) to <math>a,b</math> respectively. Notice that the differences <math>c = a-mq</math> and <math>d = b-nq</math> are integers of absolute value strictly less than <math>q/2</math>: indeed, when <math> q > 2 </math> is even, gcd<math>(a,q/2)=1</math>; otherwise since gcd<math>(a,q/2) \mid q/2 \mid q \mid a^2+b^2</math>, we would also have gcd<math>(a,q/2) \mid b</math>.

::Multiplying out we obtain
:::<math>a^2 + b^2 = m^2q^2 + 2mqc + c^2 + n^2q^2 + 2nqd + d^2 = Aq + (c^2+d^2)</math>
::uniquely defining a non-negative integer <math>A</math>. Since <math>q</math> divides both ends of this equation sequence it follows that <math>c^2+d^2</math> must also be divisible by <math>q</math>: say <math>c^2+d^2 = qr</math>. Let <math>g</math> be the gcd of <math>c</math> and <math>d</math> which by the co-primeness of <math>a,b</math> is relatively prime to <math>q</math>. Thus <math>g^2</math> divides <math>r</math>, so writing <math>e = c/g</math>, <math>f = d/g</math> and <math>s = r/g^2</math>, we obtain the expression <math>e^2+f^2 = qs</math> for relatively prime <math>e</math> and <math>f</math>, and with <math> s < q/2 </math>, since
:::<math>qs = e^2 + f^2 \leq c^2+d^2 < \left(\frac{q}{2}\right)^2 + \left(\frac{q}{2}\right)^2 = q^2/2.</math>

::Now finally, the ''descent'' step: if <math>q</math> is not the sum of two squares, then by step (3.) there must be a factor <math>q_1</math> say of <math>s</math> which is not the sum of two squares. But <math>q_1 \leq s < q/2 < q </math> and so repeating these steps (initially with <math>e,f;q_1</math> in place of <math>a,b;q</math>, and so on ''ad infinitum'') we shall be able to find a strictly decreasing infinite sequence <math>q, q_1, q_2, \ldots </math> 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 <math>q</math> must be expressible as a sum of two squares, as claimed.

5. ''Every prime of the form <math>4n+1</math> is a sum of two squares.''
(This is the main result of Euler's second paper).

::If <math>p=4n+1</math>, then by [[Fermat's Little Theorem]] each of the numbers <math>1, 2^{4n}, 3^{4n},\dots, (4n)^{4n}</math> is congruent to one modulo <math>p</math>. The differences <math>2^{4n}-1, 3^{4n}-2^{4n},\dots,(4n)^{4n}-(4n-1)^{4n}</math> are therefore all divisible by <math>p</math>. Each of these differences can be factored as
:::<math>a^{4n}-b^{4n} = \left(a^{2n}+b^{2n}\right)\left(a^{2n}-b^{2n}\right).</math>
::Since <math>p</math> is prime, it must divide one of the two factors. If in any of the <math>4n-1</math> cases it divides the first factor, then by the previous step we conclude that <math>p</math> is itself a sum of two squares (since <math>a</math> and <math>b</math> differ by <math>1</math>, they are relatively prime). So it is enough to show that <math>p</math> cannot always divide the second factor. If it divides all <math>4n-1</math> differences <math>2^{2n}-1, 3^{2n}-2^{2n},\dots,(4n)^{2n}-(4n-1)^{2n}</math>, then it would divide all <math>4n-2</math> differences of successive terms, all <math>4n-3</math> differences of the differences, and so forth. Since the <math>k</math>th differences of the sequence <math>1^k, 2^k, 3^k,\dots</math> are all equal to <math>k!</math> ([[Finite difference#Calculus of finite differences|Finite difference]]), the <math>2n</math>th differences would all be constant and equal to <math>(2n)!</math>, which is certainly not divisible by <math>p</math>. Therefore, <math>p</math> cannot divide all the second factors which proves that <math>p</math> is indeed the sum of two squares.

===Lagrange's proof through quadratic forms===
[[Joseph Louis Lagrange|Lagrange]] completed a proof in 1775<ref>Nouv. Mém. Acad. Berlin, année 1771, 125; ibid. année 1773, 275; ibid année 1775, 351.</ref> based on his general theory of integral [[quadratic form]]s. The following presentation incorporates a slight simplification of his argument, due to [[Carl Friedrich Gauss|Gauss]], which appears in article 182 of the [[Disquisitiones Arithmeticae]].

An (integral [[binary quadratic form|binary) quadratic form]] is an expression of the form <math>ax^2 + bxy + cy^2</math> with <math>a,b,c</math> integers. A number <math>n</math> is said to be ''represented by the form'' if there exist integers <math>x,y</math> such that <math>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>p</math> is represented by the form <math>x^2 + y^2</math> (i.e., <math>a=c=1</math>, <math>b=0</math>) exactly when <math>p</math> is congruent to <math>1</math> modulo <math>4</math>.

The [[discriminant]] of the quadratic form is defined to be <math>b^2 - 4ac</math>. The discriminant of <math>x^2 + y^2</math> is then equal to <math>-4</math>.

Two forms <math> ax^2 + bxy + cy^2 </math> and <math> a'x'^2 + b'x'y' + c'y'^2 </math> are ''equivalent'' if and only if there exist substitutions with integer coefficients
: <math> x = \alpha x' + \beta y'</math>
: <math> y = \gamma x' + \delta y'</math>
with <math>\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> 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>p</math>. For example, one can use a form
:<math> px^2 + 2mxy + \left(\frac{m^2+1}{p}\right)y^2,</math>
where the first coefficient ''a''&nbsp;=&nbsp;<math>p</math> was chosen so that the form represents <math>p</math> by setting ''x''&nbsp;=&nbsp;1, and ''y''&nbsp;=&nbsp;0, the coefficient ''b''&nbsp;=&nbsp;2''m'' is an arbitrary even number (as it must be, to get an even discriminant), and finally <math> c=\frac{m^2+1}{p} </math> is chosen so that the discriminant <math> b^2-4ac=4m^2-4pc </math> is equal to −4, which guarantees that the form is indeed equivalent to <math> x^2+y^2 </math>. Of course, the coefficient <math> c=\frac{m^2+1}{p} </math> must be an integer, so the problem is reduced to finding some integer ''m'' such that <math>p</math> divides <math>m^2+1</math>: or in other words, a '' 'square root of -1 modulo <math>p</math>' ''.

We claim such a square root of <math>-1</math> is given by <math> K = \prod_{k=1}^\frac{p-1}{2} k </math>. Firstly it follows from Euclid's [[Fundamental Theorem of Arithmetic]] that <math> ab \equiv 0 \pmod p \iff a \equiv 0 \pmod p \ \ \hbox{or}\ \ b \equiv 0 \pmod p </math>. Consequently, <math> a^2 \equiv 1 \pmod p \iff a \equiv \pm 1 \pmod p </math>: that is, <math> \pm 1 </math> are their own inverses modulo <math>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>p</math> is prime, that for every <math> 2 \leq a \leq p-2 </math> the gcd of <math>a</math> and <math>p</math> may be expressed via the [[Euclidean algorithm]] yielding a unique and ''distinct'' inverse <math> a^{-1} \neq a </math> of <math>a</math> modulo <math>p</math>. In particular therefore the product of ''all'' non-zero residues modulo <math>p</math> is <math>-1</math>. Let <math> L = \prod_{l=\frac{p+1}{2}}^{p-1} l </math>: from what has just been observed, <math> KL \equiv -1 \pmod p </math>. But by definition, since each term in <math>K</math> may be paired with its negative in <math>L</math>, <math> L = (-1)^\frac{p-1}{2}K </math>, which since <math>p</math> is odd shows that <math> K^2 \equiv -1 \pmod p \iff p \equiv 1 \pmod 4 </math>, as required.
<!--
This is possible by [[Euler's criterion]], but we reproduce the argument below to finish the proof.

As said, it suffices to find a root ''m'' of the polynomial <math> P(x)=x^2+1 </math> modulo ''p''&nbsp;=&nbsp;4''n''+1. What we do know, by Fermat's Little Theorem, is that each ''z'' not congruent to 0 modulo ''p'' is a root of the polynomial <math> Q(z)=z^{p-1}-1 = z^{4n}-1 = (z^{2n}-1)(z^{2n}+1)</math>. Then it must be a root of either <math> z^{2n}-1 </math> or <math> z^{2n}+1 </math>, since the integers modulo ''p'' form a field. Moreover, by a theorem of Lagrange, the number of roots modulo ''p'' of a polynomial of degree ''d'' is at most ''d'' (this follows again since the integers modulo ''p'' form a field). So the 4''n'' nonzero classes 1, 2, …, ''p''&nbsp;−&nbsp;1 must split into exactly 2''n'' of them that are roots of <math>z^{2n} - 1 </math>, and the other 2''n'' that are roots of <math> z^{2n} + 1 </math>. Choosing any ''z'' of the second kind and setting <math>m=z^n</math> completes the proof.
-->

===Dedekind's two proofs using Gaussian integers===
[[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 {{math|''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 {{mvar|p}} is an odd [[prime number]], then we have <math>i^{p-1} = (-1)^{\frac{p-1}{2}}</math> in the Gaussian integers. Consequently, writing a Gaussian integer {{math|1=''ω'' = ''x'' + ''iy''}} with {{math|''x,y'' ∈ '''Z'''}} and applying the [[Frobenius automorphism]] in '''Z'''[''i'']/(''p''), one finds
:<math>\omega^p = (x+yi)^p \equiv x^p+y^pi^p \equiv x + (-1)^{\frac{p-1}{2}}yi \pmod{p},</math>
since the automorphism fixes the elements of '''Z'''/(''p''). In the current case, <math>p=4n+1</math> for some integer n, and so in the above expression for ω<sup>p</sup>, the exponent {{tmath|(p-1)/2}} of &minus;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 {{math|''f'' ∈ {{mset|1,2}}}} is the [[order (group theory)|order]] of the Frobenius automorphism of '''Z'''[''i'']/(''p''), then the [[ideal (ring theory)|ideal]] <math>(p)</math> in '''Z'''[''i''] would be a product of 2/''f'' distinct [[prime ideal]]s. (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 {{math|''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>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>\alpha</math> of one of the ideal factors of (''p'') must be a strict divisor of <math>N(p) = p^2</math>, so that we must have <math> 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>p=4n+1</math> is a prime number, then there must be an integer ''m'' such that <math>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 {{math|''p'' ∈ '''Z'''}} does not divide either of the Gaussian integers <math>m + i</math> and <math>m-i</math> (as it does not divide their [[imaginary part]]s), but it does divide their product <math>m^2 + 1</math>, it follows that {{mvar|p}} cannot be a [[integral domain#Divisibility, prime and irreducible elements|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>p^2 = N(p)</math>, there can only be up to two factors of p), so it must be of the form <math>p = (x+yi)(x-yi)</math> for some integers {{mvar|x}} and {{mvar|y}}. This immediately yields that <math>p = x^2 + y^2</math>.

===Proof by Minkowski's Theorem===
For <math>p</math> congruent to <math>1</math> mod <math>4</math> a prime, <math>-1</math> is a [[quadratic residue]] mod <math>p</math> by [[Euler's criterion]]. Therefore, there exists an integer <math>m</math> such that <math>p</math> divides <math>m^2+1</math>. Let <math>\hat{i}, \hat{j}</math> be the [[standard basis]] elements for the [[vector space]] <math>\mathbb{R}^2</math> and set <math>\vec{u} = \hat{i} + m\hat{j}</math> and <math>\vec{v} = 0\hat{i} + p\hat{j}</math>. Consider the [[lattice (group)|lattice]] <math>S = \{a\vec{u} + b\vec{v} \mid a, b \in \mathbb Z\}</math>. If <math>\vec{w} = a\vec{u} + b\vec{v} = a \hat{i} + (am + bp)\hat{j} \in S</math> then <math>\|\vec{w}\|^2 \equiv a^2 + (am+bp)^2 \equiv a^2(1 + m^2) \equiv 0\pmod{p}</math>. Thus <math>p</math> divides <math>\|\vec{w}\|^2</math> for any <math>\vec{w} \in S</math>.

The area of the [[primitive cell#Two dimensions|fundamental parallelogram]] of the lattice is <math>p</math>. The area of the open disk, <math>D</math>, of radius <math>\sqrt{2p}</math> centered around the origin is <math>2 \pi p > 4p</math>. Furthermore, <math>D</math> is convex and symmetrical about the origin. Therefore, by [[Minkowski's theorem]] there exists a nonzero vector <math>\vec{w} \in S</math> such that <math>\vec{w} \in D</math>. Both <math>\|\vec{w}\|^2 < 2p</math> and <math>p \mid \|\vec{w}\|^2</math> so <math>p = \|\vec{w}\|^2</math>. Hence <math>p</math> is the sum of the squares of the components of <math>\vec{w}</math>.

===Zagier's "one-sentence proof"===
Let <math>p=4k+1</math> be prime, let <math>\mathbb{N}</math> denote the [[natural number]]s (with or without zero), and consider the finite set <math>S=\{(x,y,z)\in\mathbb{N}^3: x^2+4yz=p\}</math> of triples of numbers.
Then <math>S</math> has two [[involution (mathematics)|involutions]]: an obvious one <math>(x,y,z)\mapsto (x,z,y)</math> whose fixed points <math>(x,y,y)</math> correspond to representations of <math>p</math> as a sum of two squares, and a more complicated one,
: <math> (x,y,z)\mapsto
\begin{cases}
(x+2z,~z,~y-x-z),\quad \textrm{if}\,\,\, x < y-z \\
(2y-x,~y,~x-y+z),\quad \textrm{if}\,\,\, y-z < x < 2y\\
(x-2y,~x-y+z,~y),\quad \textrm{if}\,\,\, x > 2y
\end{cases}
</math>
which has exactly one fixed point <math>(1,1,k)</math>. This proves that the cardinality of <math>S</math> is odd. Hence, <math>S</math> has also a fixed point with respect to the obvious involution.

This proof, due to [[Don Zagier|Zagier]], is a simplification of an earlier proof by [[Roger Heath-Brown|Heath-Brown]], which in turn was inspired by a proof of [[Joseph Liouville|Liouville]]. The technique of the proof is a combinatorial analogue of the topological principle that the [[Euler characteristic]]s of a [[topological space]] with an involution and of its [[fixed-point theorem|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 [https://mathoverflow.net/questions/31113/zagiers-one-sentence-proof-of-a-theorem-of-fermat/299696#299696 MathOverflow post] by Moritz Firsching and this [https://www.youtube.com/watch?v=DjI1NICfjOk YouTube video] by [[Burkard Polster|Mathologer]].

===Proof with partition theory===
In 2016, A. David Christopher gave a [[partition (number theory)|partition-theoretic]] proof by considering partitions of the odd prime <math>n</math> having exactly two sizes <math>a_i (i=1,2)</math>, each occurring exactly <math> a_i</math> times, and by showing that at least one such partition exists if <math>n</math> is congruent to 1 modulo 4.<ref>A. David Christopher, A partition-theoretic proof of Fermat's Two Squares Theorem", Discrete Mathematics, 339 (2016) 1410–1411.</ref>

==See also==
* [[Legendre's three-square theorem]]
* [[Lagrange's four-square theorem]]
* [[Landau–Ramanujan constant]]
* [[Thue's lemma]]
* [[Friedlander–Iwaniec theorem]]

==References==
{{Refbegin}}
*{{cite book | author = D. A. Cox | author-link=David A. Cox | title = Primes of the Form x<sup>2</sup>&nbsp;+&nbsp;ny<sup>2</sup>| publisher = Wiley-Interscience | year = 1989 | isbn=0-471-50654-0 }}*Richard Dedekind, ''The theory of algebraic integers''.
*[[L. E. Dickson]]. ''[[History of the Theory of Numbers]]'' Vol. 2. Chelsea Publishing Co., New York 1920
*[[Harold Edwards (mathematician)|Harold M. Edwards]], ''Fermat's Last Theorem. A genetic introduction to algebraic number theory''. Graduate Texts in Mathematics no. 50, Springer-Verlag, NY, 1977.
*C. F. Gauss, ''[[Disquisitiones Arithmeticae]]'' (English Edition). Transl. by Arthur A. Clarke. Springer-Verlag, 1986.
*{{Citation|last=Goldman|first=Jay R.|year=1998|title=The Queen of Mathematics: A historically motivated guide to Number Theory|publisher=[[A K Peters, Ltd.|A K Peters]]|isbn=1-56881-006-7|url-access=registration|url=https://archive.org/details/queenofmathemati0000gold}}
*D. R. Heath-Brown, ''Fermat's two squares theorem''. Invariant, 11 (1984) pp.&nbsp;3–5.
*[[John Stillwell]], Introduction to ''Theory of Algebraic Integers'' by Richard Dedekind. Cambridge Mathematical Library, Cambridge University Press, 1996.  {{ISBN|0-521-56518-9}}
*[[Don Zagier]], ''A one-sentence proof that every prime p ≡ 1 mod 4 is a sum of two squares''. Amer. Math. Monthly 97 (1990), no. 2, 144, {{doi|10.2307/2323918}}
{{Refend}}

==Notes==
{{Reflist}}

==External links==
*[https://web.archive.org/web/20121117120257/http://planetmath.org/encyclopedia/ProofOfThuesLemma.html Two more proofs at PlanetMath.org]
*{{cite web|url=http://www.math.unh.edu/~dvf/532/Zagier|title=A one-sentence proof of the theorem|url-status=unfit|archive-url=https://web.archive.org/web/20120205194801/http://www.math.unh.edu/~dvf/532/Zagier|archive-date=5 February 2012}}
*[https://ora.ox.ac.uk/objects/uuid:c91a3bdd-7d8a-4bea-9734-28caf66f0914 Fermat's two squares theorem], D. R. Heath-Brown, 1984.
* [[Burkard Polster|Polster, Burkard]] (2019) [https://www.youtube.com/watch?v=00w8gu2aL-w "Fermat's Christmas theorem: Visualising the hidden circle in π/4 = 1 − 1/3 + 1/5 − 1/7 + ..."] (Video). ''Mathologer''.


{{Pierre de Fermat}}

[[Category:Additive number theory]]
[[Category:Squares in number theory]]
[[Category:Theorems in number theory]]