Math 2.0

Number theory Proof

Proof of the first supplement to quadratic reciprocity from Euler's criterion

Builds on Legendre symbolEuler's criterionCongruence modulo n

Proof

  1. Let pp be an odd prime. Then (p−1)/2(p-1)/2 is a natural number.
  2. By Euler's criterion with a=−1a = -1, (−1p)≡(−1)(p−1)/2(modp)\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod p.
  3. Since p∤−1p \nmid -1, the Legendre symbol (−1p)\left(\frac{-1}{p}\right) is 11 or −1-1. Also (−1)(p−1)/2(-1)^{(p-1)/2} is 11 or −1-1.
  4. So the two sides of step 2 differ by 00 or by ±2\pm 2. Since p≥3p \ge 3 divides the difference, the difference is 00.
  5. Hence (−1p)=(−1)(p−1)/2\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}.

Idea

Euler's criterion computes the symbol as (−1)(p−1)/2(-1)^{(p-1)/2} modulo pp. Both sides are signs, and two signs that agree modulo an odd prime are equal.

Reading path

To understand this page from the ground up, read these 75 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 of Euclid's lemma, Proof that R[x] is an integral domain iff R is, Proof of the degree of a product over an integral domain, Proof of strong induction from ordinary induction, Proof that the integers modulo a prime form a field, Proof that congruence is compatible with addition, Proof of Euler's criterion by counting quadratic residues, 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 well-ordering principle from strong induction, Proof of the division algorithm, Proof of the factor theorem, Proof that congruence is compatible with powers.

  1. Definition by recursion concept
  2. Divisibility definition
  3. Group concept
  4. Mathematical induction concept
  5. Natural numbers object
  6. Peano axioms concept
  7. Congruence modulo n definition
  8. Greatest common divisor definition
  9. Prime number definition
  10. Ring definition
  11. Successor function definition
  12. Quadratic residue definition
  13. Residue class definition
  14. Proof that congruence is compatible with addition proof
  15. Proof that congruence is compatible with multiplication proof
  16. Coprime integers definition
  17. Addition of natural numbers definition
  18. Commutative ring definition
  19. Polynomial ring definition
  20. Ring homomorphism definition
  21. Unit of a ring definition
  22. Zero divisor definition
  23. The successor function is injective statement
  24. Zero is not a successor statement
  25. Congruence is compatible with addition statement
  26. Legendre symbol definition
  27. Congruence is compatible with multiplication statement
  28. Proof of the commutativity of addition by induction proof
  29. Order on the natural numbers definition
  30. Divisibility in a commutative ring definition
  31. Degree of a polynomial definition
  32. Polynomial evaluation definition
  33. Field definition
  34. Integral domain definition
  35. Integers modulo n definition
  36. Proof that congruence is compatible with powers proof
  37. Commutativity of addition statement
  38. Leading coefficient definition
  39. Proof of cancellation in an integral domain proof
  40. Proof of strong induction from ordinary induction proof
  41. Root of a polynomial definition
  42. Evaluation homomorphism definition
  43. Congruence is compatible with powers statement
  44. Monic polynomial definition
  45. Strong induction statement
  46. Multiplicity of a root definition
  47. Proof of the degree of a product over an integral domain proof
  48. Cancellation in an integral domain statement
  49. Proof of the remainder theorem proof
  50. Proof of the well-ordering principle from strong induction proof
  51. Division algorithm for polynomials statement
  52. Degree of a product statement
  53. Well-ordering principle statement
  54. Remainder theorem statement
  55. Proof that R[x] is an integral domain iff R is proof
  56. Proof of the division algorithm proof
  57. Proof of the factor theorem proof
  58. R[x] is an integral domain iff R is statement
  59. Division algorithm statement
  60. Factor theorem statement
  61. Proof of Bézout's identity proof
  62. Proof that a polynomial over a field has at most as many roots as its degree proof
  63. Bézout's identity statement
  64. A polynomial over a field has at most as many roots as its degree statement
  65. Proof that the integers modulo a prime form a field proof
  66. Proof of the generalized Euclid's lemma proof
  67. Integers modulo a prime form a field statement
  68. Generalized Euclid's lemma statement
  69. Proof of Euclid's lemma proof
  70. Euclid's lemma statement
  71. Proof of Fermat's little theorem by rearrangement proof
  72. Fermat's little theorem statement
  73. Proof of Euler's criterion by counting quadratic residues proof
  74. Euler's criterion statement
  75. Proof of the first supplement to quadratic reciprocity from Euler's criterion proof

Where this leads

20 pages build on this one.

Further reading

  1. Web https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Raji)/05%3A_Primitive_Roots_and_Quadratic_Residues/5.05%3A_Legendre_Symbol
About this page
TagSE10J87AHN
URIm2://SE10J87AHN
Kindproof
WritingW0 stub
MSC11A15
ProvesFirst supplement to quadratic reciprocity
UsesLegendre symbol, Euler's criterion, 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.