Math 2.0

Number theory Proof

Proof of Fermat's theorem on sums of two squares by Thue's lemma

Builds on Prime numberFirst supplement to quadratic reciprocityLegendre symbolQuadratic residuePigeonhole principleIrrationality of square roots of non-squaresCongruence modulo n

Proof

Let pp be an odd prime. Congruences are modulo the stated modulus.

If p=x2+y2p = x^2 + y^2, then p≡1(mod4)p \equiv 1 \pmod 4.

  1. An even integer 2k2k has square 4k2≡0(mod4)4k^2 \equiv 0 \pmod 4. An odd integer 2k+12k + 1 has square 4k2+4k+1≡1(mod4)4k^2 + 4k + 1 \equiv 1 \pmod 4.
  2. So x2+y2x^2 + y^2 is 00, 11 or 22 modulo 44.
  3. Since pp is odd, pp is 11 or 33 modulo 44. With p=x2+y2p = x^2 + y^2, step 2 leaves only p≡1(mod4)p \equiv 1 \pmod 4.

If p≡1(mod4)p \equiv 1 \pmod 4, then p=x2+y2p = x^2 + y^2.

  1. Since (p−1)/2(p - 1)/2 is even, the first supplement to quadratic reciprocity gives (−1p)=1\left(\frac{-1}{p}\right) = 1, a Legendre symbol.
  2. So −1-1 is a quadratic residue modulo pp: there is an integer aa with a2≡−1(modp)a^2 \equiv -1 \pmod p.
  3. Let kk be the largest integer with k2≤pk^2 \le p. Since pp is prime, it is not a perfect square, so k<p<k+1k < \sqrt p < k + 1 by irrationality of square roots of non-squares.
  4. Let SS be the set of pairs (u,v)(u, v) of integers with 0≤u,v≤k0 \le u, v \le k. It has (k+1)2>p(k + 1)^2 > p elements.
  5. Map (u,v)(u, v) to the residue of u−avu - av modulo pp. There are only pp residues. By the pigeonhole principle, two distinct pairs (u,v)≠(u′,v′)(u, v) \ne (u', v') have u−av≡u′−av′u - av \equiv u' - av'.
  6. Put x=u−u′x = u - u' and y=v−v′y = v - v'. Then x≡ay(modp)x \equiv ay \pmod p, the pair (x,y)(x, y) is not (0,0)(0, 0), and ∣x∣,∣y∣≤k\abs{x}, \abs{y} \le k.
  7. By steps 5 and 9, x2+y2≡a2y2+y2=(a2+1)y2≡0(modp)x^2 + y^2 \equiv a^2y^2 + y^2 = (a^2 + 1)y^2 \equiv 0 \pmod p.
  8. By steps 6 and 9, 0<x2+y2≤2k2<2p0 < x^2 + y^2 \le 2k^2 < 2p.
  9. The only multiple of pp strictly between 00 and 2p2p is pp. So p=x2+y2p = x^2 + y^2.

Idea

Squares are 00 or 11 modulo 44, which gives one direction. For the other, −1-1 is a square a2a^2 modulo pp. The pigeonhole principle finds small xx and yy with x≡ayx \equiv ay, so pp divides x2+y2x^2 + y^2, and smallness forces x2+y2=px^2 + y^2 = p.

Reading path

To understand this page from the ground up, read these 130 pages in order. The foundations come first. The path takes the proofs Proof of Bézout's identity, Proof of cancellation in an integral domain, Proof of the generalized Euclid's lemma, Proof of the commutativity of addition by induction, Proof of Fermat's little theorem by rearrangement, Proof that a composition of injections is injective, Proof of Euclid's lemma, Proof that R[x] is an integral domain iff R is, Proof that a function is bijective iff it has a two-sided inverse, Proof of the degree of a product over an integral domain, Proof of strong induction from ordinary induction, Proof of the fundamental theorem of arithmetic, Proof of the complement principle, Proof of the pigeonhole principle, Proof that the integers modulo a prime form a field, Proof that a composition of surjections is surjective, Proof that congruence is compatible with addition, Proof of Euler's criterion by counting quadratic residues, Proof of the existence of prime factorization, Proof that a polynomial over a field has at most as many roots as its degree, Proof of the remainder theorem, Proof that congruence is compatible with multiplication, Proof of the rule of sum, Proof of the well-ordering principle from strong induction, Proof of the division algorithm, Proof of the first supplement to quadratic reciprocity from Euler's criterion, Proof of the bijection principle, Proof of the irrationality of square roots of non-squares, Proof of the factor theorem, Proof of the existence of a prime divisor, Proof that congruence is compatible with powers.

  1. Cardinality of a finite set definition
  2. Definition by recursion concept
  3. Divisibility definition
  4. Element definition
  5. Group concept
  6. Mathematical induction concept
  7. Natural numbers object
  8. Peano axioms concept
  9. Proposition concept
  10. Rational numbers object
  11. Real numbers object
  12. Congruence modulo n definition
  13. Greatest common divisor definition
  14. Prime number definition
  15. Set definition
  16. Ring definition
  17. Successor function definition
  18. Conjunction definition
  19. Implication definition
  20. Predicate definition
  21. Irrational number definition
  22. Quadratic residue definition
  23. Residue class definition
  24. Coprime integers definition
  25. Proof that congruence is compatible with addition proof
  26. Proof that congruence is compatible with multiplication proof
  27. Prime factorization definition
  28. Empty set object
  29. Ordered pair definition
  30. Addition of natural numbers definition
  31. Commutative ring definition
  32. Intersection definition
  33. Polynomial ring definition
  34. Ring homomorphism definition
  35. Unit of a ring definition
  36. Zero divisor definition
  37. The successor function is injective statement
  38. Zero is not a successor statement
  39. Existential quantifier definition
  40. Universal quantifier definition
  41. Legendre symbol definition
  42. Congruence is compatible with addition statement
  43. Congruence is compatible with multiplication statement
  44. Proof of the commutativity of addition by induction proof
  45. Cartesian product definition
  46. Order on the natural numbers definition
  47. Subset definition
  48. Disjoint sets definition
  49. Divisibility in a commutative ring definition
  50. Degree of a polynomial definition
  51. Field definition
  52. Polynomial evaluation definition
  53. Integral domain definition
  54. Uniqueness quantifier definition
  55. Integers modulo n definition
  56. Proof that congruence is compatible with powers proof
  57. Binary relation definition
  58. Commutativity of addition statement
  59. Proof of cancellation in an integral domain proof
  60. Leading coefficient definition
  61. Proof of strong induction from ordinary induction proof
  62. Root of a polynomial definition
  63. Evaluation homomorphism definition
  64. Congruence is compatible with powers statement
  65. Monic polynomial definition
  66. Strong induction statement
  67. Function definition
  68. Cancellation in an integral domain statement
  69. Multiplicity of a root definition
  70. Proof of the degree of a product over an integral domain proof
  71. Proof of the remainder theorem proof
  72. Codomain definition
  73. Function composition definition
  74. Identity function definition
  75. Injective function definition
  76. Image of a set definition
  77. Proof of the well-ordering principle from strong induction proof
  78. Division algorithm for polynomials statement
  79. Degree of a product statement
  80. Left inverse definition
  81. Right inverse definition
  82. Surjective function definition
  83. Proof that a composition of injections is injective proof
  84. Well-ordering principle statement
  85. Remainder theorem statement
  86. Proof that R[x] is an integral domain iff R is proof
  87. Proof that a composition of surjections is surjective proof
  88. Composition of injections is injective statement
  89. Bijective function definition
  90. Proof of the existence of a prime divisor proof
  91. Proof of the division algorithm proof
  92. Proof of the factor theorem proof
  93. R[x] is an integral domain iff R is statement
  94. Composition of surjections is surjective statement
  95. Proof that a function is bijective iff it has a two-sided inverse proof
  96. Existence of a prime divisor statement
  97. Division algorithm statement
  98. Proof of the rule of sum proof
  99. Factor theorem statement
  100. Bijective iff it has a two-sided inverse statement
  101. Rule of sum statement
  102. Proof of Bézout's identity proof
  103. Proof of the existence of prime factorization proof
  104. Proof that a polynomial over a field has at most as many roots as its degree proof
  105. Proof of the bijection principle proof
  106. Bézout's identity statement
  107. Proof of the complement principle proof
  108. Existence of prime factorization statement
  109. A polynomial over a field has at most as many roots as its degree statement
  110. Bijection principle statement
  111. Complement principle statement
  112. Proof of the generalized Euclid's lemma proof
  113. Proof that the integers modulo a prime form a field proof
  114. Integers modulo a prime form a field statement
  115. Generalized Euclid's lemma statement
  116. Proof of the pigeonhole principle proof
  117. Pigeonhole principle statement
  118. Proof of Euclid's lemma proof
  119. Euclid's lemma statement
  120. Proof of Fermat's little theorem by rearrangement proof
  121. Proof of the fundamental theorem of arithmetic proof
  122. Fermat's little theorem statement
  123. Fundamental theorem of arithmetic statement
  124. Proof of Euler's criterion by counting quadratic residues proof
  125. Proof of the irrationality of square roots of non-squares proof
  126. Euler's criterion statement
  127. Irrationality of square roots of non-squares statement
  128. Proof of the first supplement to quadratic reciprocity from Euler's criterion proof
  129. First supplement to quadratic reciprocity statement
  130. Proof of Fermat's theorem on sums of two squares by Thue's lemma proof

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Thue%27s_lemma
About this page
Tag7AAS7DK6MA
URIm2://7AAS7DK6MA
Kindproof
WritingW0 stub
MSC11E25
ProvesFermat's theorem on sums of two squares
UsesPrime number, First supplement to quadratic reciprocity, Legendre symbol, Quadratic residue, Pigeonhole principle, Irrationality of square roots of non-squares, Congruence modulo n
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.