Number theory

Builds on

Required prerequisites, all the way down: 17

You will learn to

• Prove that (ℤ/pℤ)ˣ is cyclic for p prime and find primitive roots.
• Compute Legendre symbols and apply the law of quadratic reciprocity.
• Characterise the primes that are sums of two squares, and solve Pell's equation using continued fractions.

Definition

• a is a quadratic residue modulo p if x² ≡ a (mod p) has a solution.
• The Legendre symbol (a/p) is 0, 1 or −1 according as p divides a, a is a non-zero quadratic residue, or a is a non-residue.
• A primitive root modulo n is a generator of the group (ℤ/nℤ)ˣ.

Theorem

• Quadratic reciprocity: for distinct odd primes p and q, (p/q)(q/p) = (−1)^(((p−1)/2)((q−1)/2)).
• An odd prime p is a sum of two squares if and only if p ≡ 1 (mod 4).
• Primitive roots modulo n exist exactly when n is 1, 2, 4, pᵏ or 2pᵏ for an odd prime p.
• For every positive integer d that is not a square, x² − dy² = 1 has infinitely many integer solutions.

Common misconceptions

• Assuming every modulus has a primitive root; modulo 8 there is none.
• Treating quadratic reciprocity as an isolated trick; it has many proofs and far-reaching generalisations.

Leads to

Optional discoveries

• Cryptography Diffie–Hellman key exchange works in a large cyclic group, such as the units modulo a prime with a primitive root as generator.
• Fields and Galois theory Quadratic reciprocity can be proved with Gauss sums and cyclotomic fields.
• ← The Pythagorean theorem

Learning pathways

• Undergraduate mathematics major

Further reading

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (1938)