The Integers and Modular Arithmetic

The integers are the first nontrivial algebraic object and the prototype for most of what follows. Their divisibility theory — the division algorithm, the Euclidean algorithm, Bézout's identity, unique factorization — reappears almost verbatim for polynomial rings and, abstractly, for Euclidean domains. Quotienting $\mathbb{Z}$ by congruence produces $\mathbb{Z}/n\mathbb{Z}$, the first finite arithmetic, and inside it the units form the first interesting finite group. Everything here rests on one axiom about how the positive integers are ordered.

Well-ordering and induction

The integers themselves are not well-ordered (they descend forever), and neither are the positive rationals (the set $\{1,1/2,1/3,\dots \}$ has no least member). Well-ordering is a genuine property of ${\mathbb{Z}}^{+}$, and it is logically equivalent to the principle that lets us prove statements about all positive integers at once.

The base case anchors the chain; the inductive step carries each case to the next. A frequently more convenient variant strengthens the hypothesis:

Strong induction lets the step invoke every earlier case, not just the immediate predecessor — exactly what a recursive procedure like the Euclidean algorithm needs. Well-ordering, ordinary induction, and strong induction are three statements of one fact: a descending chain of positive integers must terminate.

The proof is the standard template: were $S$ to have no least element, one shows by strong induction that no integer below any given bound can lie in $S$, forcing $S=\varnothing$, a contradiction. We take well-ordering as the starting axiom and derive everything downstream from it.

The division algorithm

Long division, made exact and unique.

The remainder is what is left after subtracting off as many copies of $b$ as fit. On the number line, the multiples of $b$ chop the line into intervals of length $b$; the integer $a$ falls into exactly one of them, and $r$ measures how far $a$ sits past the multiple on its left.

Existence and uniqueness is the model well-ordering argument. For existence, consider the set $S=\{a-bk\mid k\in \mathbb{Z},a-bk\ge 0\}$ of nonnegative values $a$ leaves after subtracting multiples of $b$. $S$ is nonempty (take $k$ very negative), so by well-ordering it has a least element $r=a-bq$. Then $r\ge 0$; and $r<b$, since $r\ge b$ would put $a-b(q+1)=r-b\ge 0$ into $S$ below $r$, contradicting minimality. For uniqueness, if $bq+r=b{q}^{\prime }+r^{\prime }$ with both remainders in $[0,b)$, then $b(q-q^{\prime })=r^{\prime }-r$, so $b\mid (r^{\prime }-r)$; but $|r^{\prime }-r|<b$ forces $r^{\prime }-r=0$, hence $r=r^{\prime }$ and $q=q^{\prime }$.⁴

Divisibility and greatest common divisors

For integers $a,b$, we write $a\mid b$ ($a$ divides $b$) when $b=ac$ for some $c\in \mathbb{Z}$. Divisibility is reflexive and transitive, and it respects integer combinations: if $k\mid a$ and $k\mid b$, then $k\mid (as+bt)$ for all $s,t\in \mathbb{Z}$. This last fact drives every gcd argument below.

Condition (ii) is stronger than $d$ is the largest common divisor by size: it says $d$ is divisible by every other common divisor. The two descriptions agree for the integers, but (ii) is the version that carries over to general rings.

The Euclidean algorithm

Computing $\gcd (a,b)$ by listing divisors is hopeless for large inputs. Iterating the division algorithm is fast. The key identity is that dividing $a$ by $b$ leaves the gcd unchanged:

because $r=a-bq$ is an integer combination of $a$ and $b$ (so common divisors of $a,b$ divide $r$), and symmetrically $a=bq+r$ shows common divisors of $b,r$ divide $a$; the two pairs have identical common divisors. Replacing $(a,b)$ by the smaller pair $(b,r)$ and repeating drives the remainder strictly down, $|b|>r_0>r_1>\cdots \ge 0$, a descending chain of nonnegative integers that must hit $0$. The last nonzero remainder is the gcd.⁵

Running the recursion the other way expresses the gcd back in terms of $a$ and $b$, which the extended algorithm tracks directly.

Bézout's identity

The extended algorithm's output is a theorem in its own right.

The second sentence gives a slick proof independent of the algorithm. Let $S=\{am+bn\mid m,n\in \mathbb{Z},am+bn>0\}$ and let $d=ar+bs$ be its least element (well-ordering again). Dividing, $a=dq+r_0$ with $0\le r_0<d$; then $r_0=a-dq=a(1-rq)+b(-sq)$ is an integer combination of $a$ and $b$, so $r_0\in S\cup \{0\}$. Being below $d$, it cannot lie in $S$, so $r_0=0$ and $d\mid a$; likewise $d\mid b$. Any common divisor $e$ of $a,b$ divides $ar+bs=d$, so $d=\gcd (a,b)$.

The coefficients $x,y$ are not unique: the general solution to $ax+by=d$ is

Bézout's identity recurs throughout elementary number theory. It gives modular inverses (below), proves Euclid's lemma (next), and explains why $a$ is invertible mod $n$ precisely when $\gcd (a,n)=1$.

Primes and unique factorization

Bézout turns the definition into the property that governs factorization.

The distinction Euclid's lemma captures, that a prime dividing a product must divide a factor, is the abstract line between irreducible and prime elements developed in the factorization chapter. In $\mathbb{Z}$ the two coincide, which is why factorization is unique.

Existence is strong induction: $n$ is prime (done) or factors as $n=n_1{n}_2$ with both smaller, each of which factors by hypothesis. Uniqueness is Euclid's lemma: if $p_1\cdots p_s=q_1\cdots q_t$, then $p_1$ divides the right side, so by the lemma it divides some $q_j$, and both being prime, $p_1=q_j$; cancel and induct. Once factorizations are unique, the gcd and lcm read off directly. Writing $a={\prod }_i{p}_i^{a_i}$ and $b={\prod }_i{p}_i^{b_i}$ over a shared prime list (zero exponents allowed),

For large integers, factoring is hard while the Euclidean algorithm is fast, so this formula is a structural identity, not a practical gcd method — a gap several modern cryptosystems are built on.

The integers modulo n

Fix $n>0$ and define $a\sim b$ when $n\mid (b-a)$. This is an equivalence relation, written $a\equiv b(\mathrm{mod}n)$ ($a$ is congruent to $b$ mod $n$). Its classes are the residue classes

and by the division algorithm every integer is congruent to exactly one of $0,1,\dots ,n-1$ (its remainder). So there are precisely $n$ classes, and they partition $\mathbb{Z}$.

These operations require a well-definedness check: the answer must not depend on which representative is chosen.

The elements of $\mathbb{Z}/n\mathbb{Z}$ are classes, not integers, so the arithmetic differs from $\mathbb{Z}$: mod $12$, the sum $\overline{5}+\overline{8}=\overline{13}=\overline{1}$, the clock-arithmetic students already know. Under addition alone, $\mathbb{Z}/n\mathbb{Z}$ is the model finite cyclic group; its addition table is a completely regular Latin square.

Units modulo n

Multiplication mod $n$ is less uniform. Some classes have multiplicative inverses and some do not. The invertible ones form a distinguished set.

Bézout identifies exactly which classes qualify.

The proof is also an algorithm: to invert $\overline{a}$, run the extended Euclidean algorithm on $a$ and $n$ to get $ax+ny=1$, and read off ${\overline{a}}^{-1}=\overline{x}$. For $n=60$ and $a=17$, the algorithm gives $(-7)(17)+(2)(60)=1$, so ${\overline{17}}^{-1}=\overline{-7}=\overline{53}$ in $\mathbb{Z}/60\mathbb{Z}$. The non-units are the classes sharing a factor with $n$; each is a zero divisor, annihilating some nonzero class ($\overline{a}\overline{b}=\overline{0}$ with $\overline{a},\overline{b}\ne \overline{0}$), so it can never be invertible.

Closure of the units under multiplication (the shaded sub-table lands inside the shaded classes) is the first observation that $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ is a group, developed in the group axioms lesson. Its size is counted by Euler's function.

For a prime $p$ every nonzero class is coprime to $p$, so $\phi (p)=p-1$ and $\mathbb{Z}/p\mathbb{Z}$ is a field. More generally $\phi (p^a)=p^a-p^{a-1}$, and $\phi$ is multiplicative on coprime arguments, $\phi (mn)=\phi (m)\phi (n)$ when $\gcd (m,n)=1$, which with the prime-power formula evaluates $\phi$ at any $n$ from its factorization.

The unit group is where modular arithmetic becomes group theory. Its order $\phi (n)$ controls the exponents that reduce to $1$, giving Fermat's little theorem and Euler's theorem once Lagrange's theorem is available, and the cyclic structure of $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ is the model finite cyclic group examined in the cyclic groups lesson.