Target Audience: Anyone comfortable with proof who wants the theory behind the arithmetic of the integers.
Prerequisites: Tier 0 — especially Proof Techniques, since induction and contradiction are used throughout, and Sets, Relations and Functions, because congruence is the equivalence relation the whole subject is built on.
This page has one destination. It starts with what it means for one integer to divide another, and ends at the Law of Quadratic Reciprocity — a result Gauss called the golden theorem and proved eight different ways. Everything between is the chain that earns it.
The pivot is Section 4. Once congruence is in place, the integers modulo \(n\) become a finite arithmetic of their own, and the rest of the page is the study of that arithmetic. The explorer in Section 9 shows it directly: the invertible residues, their orders, and which moduli have a single generator.
First unit of Tier 2, and the first tutorial in the Number Theory group. Nine proof pages sit at the far end of this ladder; each section names the one it leads to.
For integers \(a\) and \(b\), we say \(a\) divides \(b\), written \(a \mid b\), when \(b = ac\) for some integer \(c\). Note what this does not say: nothing about fractions, and nothing about size. Every integer divides \(0\), and \(1\) divides everything.
For integers \(a\) and \(b\) with \(b \gt 0\), there are unique integers \(q\) and \(r\) with \(a = qb + r\) and \(0 \leq r \lt b\).
Existence comes from taking the least non-negative element of the set \(\{a - qb\}\) — the Well-Ordering Principle. Uniqueness: if \(q_1 b + r_1 = q_2 b + r_2\) with both remainders in range, then \(b\) divides \(r_1 - r_2\), and \(|r_1 - r_2| \lt b\) forces \(r_1 = r_2\).
Despite the name it is a theorem, not an algorithm. The constraint \(0 \leq r \lt b\) is what makes the remainder well defined, and it is the reason every later definition can speak of the remainder.
The greatest common divisor \(\gcd(a, b)\) is the largest integer dividing both. Two integers are coprime when their gcd is \(1\).
The Euclidean algorithm computes it without factoring anything. Repeatedly replace the pair \((a, b)\) by \((b, a \bmod b)\); the gcd is unchanged at each step because any common divisor of \(a\) and \(b\) also divides \(a - qb\). The remainders strictly decrease, so the process stops, and the last non-zero remainder is the gcd.
So \(\gcd(1071, 462) = 21\), in three divisions rather than by factoring either number.
There exist integers \(x, y\) with \(ax + by = \gcd(a, b)\).
Run the algorithm backwards, substituting each remainder in terms of the two before it. The consequence that matters: \(\gcd(a, b) = 1\) if and only if \(ax + by = 1\) is solvable — which is exactly what a modular inverse is, in Section 5.
An integer \(p \gt 1\) is prime when its only positive divisors are \(1\) and itself; otherwise it is composite. Note \(1\) is neither — a convention that exists precisely so unique factorisation can be stated.
The Infinitude of Primes (Euclid's argument by contradiction), Euclid's Lemma — if \(p \mid ab\) then \(p \mid a\) or \(p \mid b\) — and the uniqueness half of the Fundamental Theorem of Arithmetic, which rests on that lemma.
Existence of a factorisation is easy induction. Uniqueness is not, and it fails in other number systems: among numbers of the form \(a + b\sqrt{-5}\), the number \(6\) factors two genuinely different ways. So uniqueness is a real theorem about the integers, not a bookkeeping remark — and Euclid's Lemma is what carries it.
Fix \(n \gt 0\). We write \(a \equiv b \pmod{n}\) when \(n \mid (a - b)\). Gauss introduced the notation in 1801, and it is the reason the subject looks like algebra rather than a list of divisibility tricks.
Reflexive, symmetric and transitive — so it partitions \(\mathbb{Z}\) into \(n\) residue classes, exactly as Sets, Relations and Functions describes. The class of \(a\) is the set of integers leaving the same remainder as \(a\) on division by \(n\).
Congruence also respects addition and multiplication: if \(a \equiv b\) and \(c \equiv d\), then \(a + c \equiv b + d\) and \(ac \equiv bd\). That compatibility is what lets arithmetic descend to the classes.
You may not divide a congruence freely. \(2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}\) is true, but \(3 \equiv 8 \pmod{10}\) is false. Cancelling \(c\) is valid only when \(\gcd(c, n) = 1\); in general \(ca \equiv cb \pmod{n}\) gives only \(a \equiv b \pmod{n / \gcd(c, n)}\).
Nearly every wrong proof in elementary number theory divides by something without checking this.
A residue \(a\) is a unit modulo \(n\) when it has a multiplicative inverse — some \(b\) with \(ab \equiv 1 \pmod{n}\).
\(a\) is invertible modulo \(n\) if and only if \(\gcd(a, n) = 1\).
Both directions are Bézout. If \(\gcd(a, n) = 1\) then \(ax + ny = 1\), so \(ax \equiv 1 \pmod{n}\) and \(x\) is the inverse. Conversely, if \(ab \equiv 1 \pmod{n}\) then \(ab - 1 = kn\), so \(ab - kn = 1\) and any common divisor of \(a\) and \(n\) divides \(1\).
Consequently \(ax \equiv b \pmod{n}\) has a solution exactly when \(\gcd(a, n) \mid b\), and then it has precisely \(\gcd(a, n)\) solutions modulo \(n\). When \(n\) is prime, every non-zero residue is a unit — which is why prime moduli behave so much better, and why they dominate the rest of this page.
If \(m_1, \ldots, m_k\) are pairwise coprime, then the system \(x \equiv r_i \pmod{m_i}\) has a solution, unique modulo \(M = m_1 \cdots m_k\).
\(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\), \(x \equiv 2 \pmod 7\) has the unique solution \(x \equiv 23 \pmod{105}\) — a problem posed by Sun Zi in the third century.
The construction: for each \(i\) let \(M_i = M / m_i\), take its inverse modulo \(m_i\), and take \(x = \sum r_i M_i (M_i^{-1} \bmod m_i)\). Each term is \(r_i\) modulo \(m_i\) and \(0\) modulo every other \(m_j\).
The Chinese Remainder Theorem. Its structural content is that arithmetic modulo \(M\) splits into independent arithmetic modulo each \(m_i\) — which is exactly what makes the totient multiplicative in the next section.
\(x \equiv 1 \pmod 4\) and \(x \equiv 2 \pmod 6\) has no solution at all: the first forces \(x\) odd, the second forces it even. When the moduli share a factor the system may be unsolvable, or solvable but not unique.
If \(p\) is prime and \(\gcd(a, p) = 1\), then \(a^{p - 1} \equiv 1 \pmod p\). Equivalently \(a^p \equiv a \pmod p\) for every \(a\), with no coprimality needed.
Multiplying by \(a\) permutes the non-zero residues modulo \(p\) — it is injective because \(a\) is a unit. So \(\{a, 2a, \ldots, (p - 1)a\}\) is the set \(\{1, 2, \ldots, p - 1\}\) rearranged. Multiplying each list out gives \(a^{p - 1}(p - 1)! \equiv (p - 1)!\), and \((p - 1)!\) is a unit, so it cancels.
Fermat's Little Theorem, and The Converse of Wilson's Theorem — Wilson says \((p - 1)! \equiv -1 \pmod p\) for prime \(p\), and the converse shows no composite above \(4\) does this, making it a genuine primality criterion.
\(a^{n-1} \equiv 1 \pmod n\) does not force \(n\) prime. The Carmichael numbers satisfy it for every coprime base — the smallest is \(561 = 3 \cdot 11 \cdot 17\). So Fermat gives a fast compositeness test, not a primality proof.
Euler's totient \(\varphi(n)\) counts the integers in \(1, \ldots, n\) coprime to \(n\) — equivalently, the number of units modulo \(n\). For prime \(p\), \(\varphi(p) = p - 1\).
\(\varphi\) is multiplicative on coprime arguments, and \(\varphi(p^k) = p^k - p^{k-1}\) because the multiples of \(p\) are exactly what must be removed. Together:
So \(\varphi(360) = \varphi(2^3)\varphi(3^2)\varphi(5) = 4 \cdot 6 \cdot 4 = 96\).
Euler's Theorem generalises Fermat to every modulus: if \(\gcd(a, n) = 1\) then \(a^{\varphi(n)} \equiv 1 \pmod n\). The same permutation argument works, run over the units instead of all non-zero residues.
Euler's Theorem and The Multiplicativity of Euler's Totient, which is proved from the Chinese Remainder Theorem of Section 6.
The order of a unit \(a\) modulo \(n\) is the least \(k \geq 1\) with \(a^k \equiv 1 \pmod n\). Euler's Theorem guarantees one exists, since \(k = \varphi(n)\) always works.
If \(a\) has order \(k\) then \(a^m \equiv 1\) exactly when \(k \mid m\). In particular \(k \mid \varphi(n)\). This is Lagrange's theorem for the units, and it is the reason the order column in the explorer below never contains a number that fails to divide \(\varphi(n)\).
A unit whose order is the full \(\varphi(n)\) is a primitive root: its powers run through every unit. Such a generator does not always exist.
Pick a modulus. The explorer lists every unit with its order, checks each order against \(\varphi(n)\), and marks the primitive roots — or reports that none exist.
Covered in Section 10 — come back once you have read it.
Every order, symbol and verdict is computed live — nothing is tabulated in advance.
Primitive Roots Exist Modulo Every Prime, and Gauss's classification: a primitive root exists modulo \(n\) exactly when \(n\) is \(1, 2, 4, p^k\) or \(2p^k\) for an odd prime \(p\). Try \(8\), \(12\) or \(15\) in the explorer to watch it fail.
For an odd prime \(p\), a unit \(a\) is a quadratic residue modulo \(p\) when \(x^2 \equiv a \pmod p\) has a solution. Squaring is two-to-one on the units, so exactly \((p - 1)/2\) of them are residues.
Write \(\left(\frac{a}{p}\right)\) for \(+1\) when \(a\) is a residue, \(-1\) when it is not, and \(0\) when \(p \mid a\). Euler's criterion makes it computable:
It follows from Section 9: the units form a cyclic group of even order, and the squares are exactly the even powers of a primitive root. The symbol is multiplicative, so it is determined by its values on primes.
That leaves one question, and it is the deep one: given two odd primes, how do \(\left(\frac{p}{q}\right)\) and \(\left(\frac{q}{p}\right)\) relate? There is no reason to expect any relation at all — and yet:
In words: the two symbols agree unless both \(p\) and \(q\) are \(3 \bmod 4\), in which case they differ. Gauss proved it at nineteen and returned to it eight times; over two hundred proofs are now known.
Euler's Criterion and Gauss's Lemma supplies the machinery, and The Law of Quadratic Reciprocity proves the theorem itself. Use the second half of the explorer to test it on any pair.
Reciprocity turns an intractable question into a fast computation: to decide whether \(a\) is a square modulo a large prime, flip the symbol and reduce, repeatedly, in the same spirit as the Euclidean algorithm. It is also the first case of a pattern — class field theory and the reciprocity laws that followed are a large part of modern number theory.
The chain, in the order it was built:
All nine Number Theory proof pages now have a path leading to them. The two at the far end — Quadratic Reciprocity and Gauss's classification — were previously unreachable without this groundwork.
The Euclidean algorithm and modular inverses are also the arithmetic behind public-key cryptography: RSA is Euler's theorem, applied to a modulus whose factorisation is kept secret.
| Fact | Statement | Proof page |
|---|---|---|
| Division algorithm | Unique \(q, r\) with \(a = qb + r\), \(0 \leq r \lt b\) | Section 1 above |
| Bézout | \(ax + by = \gcd(a, b)\) is solvable | Section 2 above |
| Euclid's Lemma | \(p \mid ab \Rightarrow p \mid a\) or \(p \mid b\) | Euclid's Lemma |
| Unique factorisation | Factorisation into primes is unique up to order | FTA uniqueness |
| Invertibility | \(a\) is a unit mod \(n\) iff \(\gcd(a, n) = 1\) | Section 5 above |
| Chinese Remainder | Coprime moduli: a unique solution mod the product | CRT |
| Fermat | \(a^{p - 1} \equiv 1 \pmod p\) when \(\gcd(a, p) = 1\) | Fermat's Little Theorem |
| Wilson | \((p - 1)! \equiv -1 \pmod p\) iff \(p\) is prime | Converse of Wilson |
| Totient | \(\varphi(n) = n \prod_{p \mid n} (1 - 1/p)\), multiplicative | Multiplicativity |
| Euler | \(a^{\varphi(n)} \equiv 1 \pmod n\) when \(\gcd(a, n) = 1\) | Euler's Theorem |
| Orders | \(a^m \equiv 1\) iff \(\operatorname{ord}(a) \mid m\); order divides \(\varphi(n)\) | Section 9 above |
| Primitive roots | Exist mod \(n\) iff \(n = 1, 2, 4, p^k, 2p^k\) | Existence, classification |
| Euler's criterion | \(\left(\frac{a}{p}\right) \equiv a^{(p - 1)/2} \pmod p\) | Criterion and Gauss's Lemma |
| Quadratic reciprocity | \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p - 1}{2}\frac{q - 1}{2}}\) | Quadratic Reciprocity |