---
title: The Integers and Modular Arithmetic
module: Foundations
moduleNumber: 1
lessonNumber: 2
order: 102
summary: >
  The integers carry the template every ring later imitates: well-ordering drives
  induction, induction drives the division algorithm, and division drives the
  Euclidean algorithm, gcd, Bézout's identity, and unique factorization into
  primes. Quotienting by congruence mod n builds the first finite arithmetic,
  Z/nZ, whose invertible elements form the group of units.
topics: [Foundations]
sources:
  - book: Dummit & Foote
    ref: "Ch. 0 — Preliminaries; §0.2 Properties of the Integers, §0.3 Z/nZ"
  - book: Judson
    ref: "Ch. 2 — The Integers; §2.1 Mathematical Induction, §2.2 The Division Algorithm"
draft: false
---

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](/abstract-algebra/factorization-and-polynomials/polynomial-rings-over-fields)
and, abstractly, for
[Euclidean domains](/abstract-algebra/factorization-and-polynomials/euclidean-domains-pids-ufds).
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](/abstract-algebra/groups-and-symmetry/group-axioms-and-first-examples).
Everything here rests on one axiom about how the positive integers are ordered.

## Well-ordering and induction

> **Axiom (Well-Ordering).** Every nonempty subset $A \subseteq \mathbb{Z}^{+}$
> has a least element: some $m \in A$ with $m \leq a$ for all $a \in A$.[^df-wo]

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.

> **Principle (Mathematical Induction).** Let $S(n)$ be a statement about integers
> $n$, and fix a base $n_0$. If $S(n_0)$ holds, and if $S(k) \Rightarrow S(k+1)$
> for every $k \geq n_0$, then $S(n)$ holds for all $n \geq n_0$.

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

> **Principle (Strong Induction).** With $S$ and $n_0$ as above, if $S(n_0)$ holds
> and if $S(n_0), S(n_0 + 1), \dots, S(k)$ together imply $S(k+1)$ for every
> $k \geq n_0$, then $S(n)$ holds for all $n \geq n_0$.

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.

> **Theorem (Induction implies well-ordering).** If mathematical induction holds,
> then every nonempty $S \subseteq \mathbb{N}$ contains a least element.[^judson-wo]

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.

> **Worked example.** To prove $3 \mid (n^3 - n)$ for every $n \geq 1$, induct on
> $n$. The base case $n = 1$ gives $1^3 - 1 = 0$, divisible by $3$. Assuming
> $3 \mid (k^3 - k)$,
>
> $$
> (k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3(k^2 + k).
> $$
>
> The first term is divisible by $3$ by the inductive hypothesis and the second is
> an explicit multiple of $3$, so $3 \mid ((k+1)^3 - (k+1))$. The statement holds
> for all $n \geq 1$.

## The division algorithm

Long division, made exact and unique.

> **Theorem (Division Algorithm).** For integers $a$ and $b$ with $b > 0$ there
> exist **unique** integers $q$ (the quotient) and $r$ (the remainder) with
> $$
> a = bq + r, \qquad 0 \leq r < b.
> $$
> More generally, for $b \neq 0$ the bound is $0 \leq r < |b|$.[^df-div][^judson-div]

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.

$$
% caption: With $b = 5$ and $a = 17$, the multiples of $b$ tile the line; $a$ lands in the block starting at $3b = 15$, so the quotient is $q = 3$ and the remainder $r = 2$ is the overshoot.
\begin{tikzpicture}[>=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\draw[->] (-0.3,0) -- (9.0,0);
% ticks at multiples of b: 0,5,10,15,20 -> x = 0,2,4,6,8
\foreach \x in {0,2,4,6,8} \draw[black] (\x,0.14) -- (\x,-0.14);
% shade the block [3b,4b)
\fill[acc!12] (6,-0.05) rectangle (8,0.05);
\node[anchor=north, font=\footnotesize] at (0,-0.18) {$0$};
\node[anchor=north, font=\footnotesize] at (2,-0.18) {$b$};
\node[anchor=north, font=\footnotesize] at (4,-0.18) {$2b$};
\node[anchor=north, font=\footnotesize] at (6,-0.18) {$3b$};
\node[anchor=north, font=\footnotesize] at (8,-0.18) {$4b$};
% point a = 17 -> x = 6.8
\fill[acc] (6.8,0) circle (2.6pt);
\node[acc, anchor=south, font=\footnotesize] at (6.8,0.16) {$a$};
% remainder bracket from 3b to a
\draw[acc, thick] (6,-0.62) -- (6.8,-0.62);
\draw[acc] (6,-0.5) -- (6,-0.74);
\draw[acc] (6.8,-0.5) -- (6.8,-0.74);
\node[acc, anchor=north, font=\footnotesize] at (6.4,-0.66) {$r$};
\end{tikzpicture}
$$

**Existence and uniqueness** is the model well-ordering argument. For existence,
consider the set $S = \{\, a - bk \mid k \in \mathbb{Z},\ a - bk \geq 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 \geq 0$; and $r < b$, since $r \geq b$ would put $a - b(q+1) = r - b \geq 0$
into $S$ below $r$, contradicting minimality. For uniqueness, if $bq + r = bq' + r'$
with both remainders in $[0, b)$, then $b(q - q') = r' - r$, so $b \mid (r' - r)$;
but $|r' - r| < b$ forces $r' - r = 0$, hence $r = r'$ and $q = q'$.[^judson-div]

## 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.

> **Definition (Greatest common divisor).** For integers $a, b$ not both zero, the
> **greatest common divisor** $d = \gcd(a, b)$ (also written $(a, b)$) is the
> positive integer with (i) $d \mid a$ and $d \mid b$, and (ii) every common
> divisor $e$ of $a$ and $b$ satisfies $e \mid d$. When $\gcd(a, b) = 1$, the
> integers are **relatively prime** (coprime).

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:

$$
a = bq + r \quad\Longrightarrow\quad \gcd(a, b) = \gcd(b, r),
$$

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 \geq 0$, a descending chain of nonnegative
integers that must hit $0$. The last nonzero remainder is the gcd.[^df-euclid]

$$
% caption: Computing $\gcd(48, 18)$: each line divides the previous divisor by the previous remainder; the divisor-remainder pair slides down until the remainder is $0$, and the last nonzero remainder, $6$, is the gcd.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=44mm, minimum height=9mm, font=\small}]
\definecolor{acc}{HTML}{4A6FA5}
\node[box] (r1) at (0,0)    {$48 = 2 (18) + 12$};
\node[box] (r2) at (0,-1.35){$18 = 1 (12) + 6$};
\node[box] (r3) at (0,-2.70){$12 = 2 (6) + 0$};
\draw[->, acc, thick] (r1.east) .. controls (3.4,0) and (3.4,-1.35) .. (r2.east);
\draw[->, acc, thick] (r2.east) .. controls (3.4,-1.35) and (3.4,-2.70) .. (r3.east);
\node[acc, anchor=west, font=\footnotesize] at (3.5,-0.68) {divisor, remainder};
\node[acc, anchor=west, font=\footnotesize] at (3.5,-0.98) {slide down a row};
\node[anchor=west, font=\footnotesize] at (3.5,-2.70) {$\gcd = 6$};
\end{tikzpicture}
$$

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

```algorithm
caption: $\textsc{ExtendedEuclid}(a, b)$ — returns $(d, x, y)$ with $d = \gcd(a,b)$ and $ax + by = d$
require $a \geq 0$, $b \geq 0$, not both zero
if $b = 0$ then
  return $(a,\ 1,\ 0)$
$(d,\ x',\ y') \gets \textsc{ExtendedEuclid}(b,\ a \bmod b)$
$x \gets y'$
$y \gets x' - \lfloor a / b \rfloor \cdot y'$
return $(d,\ x,\ y)$
```

## Bézout's identity

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

> **Theorem (Bézout's identity).** For integers $a, b$ not both zero there exist
> integers $x, y$ with
> $$
> \gcd(a, b) = ax + by.
> $$
> The gcd is the smallest positive integer expressible as an integer combination of
> $a$ and $b$.[^df-bezout][^judson-bezout]

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 \leq 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

$$
x = x_0 + \frac{b}{d}\,t, \qquad y = y_0 - \frac{a}{d}\,t, \qquad t \in \mathbb{Z}.
$$

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$.

> **Worked example.** Compute $\gcd(252, 198)$ and write it as $252x + 198y$.
> Iterated division gives
>
> $$
> 252 = 1 \cdot 198 + 54,\quad 198 = 3 \cdot 54 + 36,\quad 54 = 1 \cdot 36 + 18,\quad 36 = 2 \cdot 18 + 0,
> $$
>
> so the last nonzero remainder is $\gcd(252, 198) = 18$. Back-substituting from the
> third line and eliminating each remainder in turn,
>
> $$
> 18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198.
> $$
>
> Thus $(x, y) = (4, -5)$, and indeed $4 \cdot 252 - 5 \cdot 198 = 1008 - 990 = 18$.

## Primes and unique factorization

> **Definition (Prime, composite).** An integer $p > 1$ is **prime** if its only
> positive divisors are $1$ and $p$; an integer $n > 1$ that is not prime is
> **composite**.

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

> **Lemma (Euclid's Lemma).** If $p$ is prime and $p \mid ab$, then $p \mid a$ or
> $p \mid b$.[^df-fta]

> **Proof.** If $p \nmid a$, then $\gcd(p, a) = 1$ (the only divisors of $p$ are $1$
> and $p$). By Bézout, $1 = px + ay$ for some $x, y$. Multiply by $b$:
> $b = pbx + aby$. Now $p \mid pbx$ and $p \mid ab$ divides $aby$, so $p$ divides the
> sum $b$. $\square$

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](/abstract-algebra/factorization-and-polynomials/euclidean-domains-pids-ufds).
In $\mathbb{Z}$ the two coincide, which is why factorization is unique.

> **Theorem (Fundamental Theorem of Arithmetic).** Every integer $n > 1$ factors
> into primes,
> $$
> n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s},
> $$
> with distinct primes $p_i$ and exponents $a_i \geq 1$, and this factorization is
> **unique** up to the order of the factors.[^df-fta]

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),

$$
\gcd(a, b) = \prod_i p_i^{\min(a_i, b_i)}, \qquad
\operatorname{lcm}(a, b) = \prod_i p_i^{\max(a_i, b_i)}, \qquad
\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab.
$$

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](/abstract-algebra/foundations/sets-functions-relations),
written $a \equiv b \pmod{n}$ ("$a$ is congruent to $b$
mod $n$"). Its classes are the **residue classes**

$$
\overline{a} = \{\, a + kn \mid k \in \mathbb{Z} \,\},
$$

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}$.

> **Definition ($\mathbb{Z}/n\mathbb{Z}$).** The quotient set of residue classes
> mod $n$ is $\mathbb{Z}/n\mathbb{Z} = \{\, \overline{0}, \overline{1}, \dots,
> \overline{n-1} \,\}$, the **integers modulo $n$**. Addition and multiplication
> are defined on representatives:
> $$
> \overline{a} + \overline{b} = \overline{a + b}, \qquad
> \overline{a} \cdot \overline{b} = \overline{ab}.
> $$

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

> **Theorem (Modular arithmetic is well defined).** If $a_1 \equiv b_1$ and
> $a_2 \equiv b_2 \pmod{n}$, then $a_1 + a_2 \equiv b_1 + b_2$ and
> $a_1 a_2 \equiv b_1 b_2 \pmod{n}$.[^df-znz]

> **Proof.** Write $a_1 = b_1 + sn$ and $a_2 = b_2 + tn$. Then
> $a_1 + a_2 = (b_1 + b_2) + (s + t)n$, congruent to $b_1 + b_2$; and
> $a_1 a_2 = b_1 b_2 + (b_1 t + b_2 s + stn)n$, congruent to $b_1 b_2$. $\square$

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](/abstract-algebra/subgroups-and-quotients/cyclic-groups); its
addition table is a completely regular Latin square.

$$
% caption: The addition table of $\mathbb{Z}/6\mathbb{Z}$. Each row is the previous shifted one step, and every residue appears once per row and once per column — the Latin-square signature of a group.
\begin{tikzpicture}[font=\small, scale=0.72]
\definecolor{acc}{HTML}{4A6FA5}
% shade the identity row and column (class 0)
\fill[acc!12] (1,-1) rectangle (7,-2);
\fill[acc!12] (1,-1) rectangle (2,-7);
% grid
\foreach \i in {0,...,7} \draw[black] (0,-\i) -- (7,-\i);
\foreach \j in {0,...,7} \draw[black] (\j,0) -- (\j,-7);
% corner
\node at (0.5,-0.5) {$+$};
% headers
\foreach \k in {0,...,5} {
  \node at (\k+1.5,-0.5) {\k};
  \node at (0.5,-\k-1.5) {\k};
}
% body: (i+j) mod 6
\foreach \i in {0,...,5} \foreach \j in {0,...,5} {
  \pgfmathtruncatemacro{\s}{mod(\i+\j,6)}
  \node at (\j+1.5,-\i-1.5) {\s};
}
\end{tikzpicture}
$$

## 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.

> **Definition (Units mod $n$).** The **group of units** is
> $$
> (\mathbb{Z}/n\mathbb{Z})^{\times} = \{\, \overline{a} \in \mathbb{Z}/n\mathbb{Z}
> \mid \overline{a}\,\overline{c} = \overline{1} \text{ for some } \overline{c} \,\},
> $$
> the residue classes with a multiplicative inverse.

Bézout identifies exactly which classes qualify.

> **Proposition (Units are the coprime classes).** $\overline{a} \in
> (\mathbb{Z}/n\mathbb{Z})^{\times}$ if and only if $\gcd(a, n) = 1$.[^df-znz]

> **Proof.** If $\gcd(a, n) = 1$, Bézout gives $ax + ny = 1$, so $ax \equiv 1
> \pmod{n}$ and $\overline{x}$ inverts $\overline{a}$. Conversely, if
> $ac \equiv 1 \pmod n$, then $ac - 1 = kn$, so $ac - kn = 1$ and any common divisor
> of $a$ and $n$ divides $1$; hence $\gcd(a, n) = 1$. $\square$

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} \neq
\overline{0}$), so it can never be invertible.

> **Worked example.** Solve $x \equiv 2 \pmod 5$ and $x \equiv 3 \pmod 7$
> together. Since $\gcd(5, 7) = 1$, Bézout gives $3 \cdot 5 - 2 \cdot 7 = 1$. The
> term $-2 \cdot 7 = -14$ is $\equiv 1 \pmod 5$ and $\equiv 0 \pmod 7$, while
> $3 \cdot 5 = 15$ is $\equiv 0 \pmod 5$ and $\equiv 1 \pmod 7$. Weighting these by
> the required residues,
>
> $$
> x = 2 \cdot (-14) + 3 \cdot 15 = -28 + 45 = 17.
> $$
>
> Then $17 \equiv 2 \pmod 5$ and $17 \equiv 3 \pmod 7$. Any two solutions differ by
> a multiple of both $5$ and $7$, hence of $35$, so the solution is
> $x \equiv 17 \pmod{35}$.

$$
% caption: Multiplication mod $8$. The shaded classes $\{1,3,5,7\}$ are the units, coprime to $8$; their products stay shaded (closure), while $0,2,4,6$ are zero divisors and never invertible.
\begin{tikzpicture}[font=\small, scale=0.66]
\definecolor{acc}{HTML}{4A6FA5}
% shade unit-by-unit interior block
\foreach \i in {1,3,5,7} \foreach \j in {1,3,5,7}
  \fill[acc!12] (\j+1,-\i-1) rectangle (\j+2,-\i-2);
% shade unit headers (row and column)
\foreach \u in {1,3,5,7} {
  \fill[acc!22] (\u+1,-1) rectangle (\u+2,0);
  \fill[acc!22] (0,-\u-1) rectangle (1,-\u-2);
}
% grid
\foreach \i in {0,...,9} \draw[black] (0,-\i) -- (9,-\i);
\foreach \j in {0,...,9} \draw[black] (\j,0) -- (\j,-9);
% corner: a small dot denotes multiplication
\fill[black] (0.5,-0.5) circle (2pt);
% headers
\foreach \k in {0,...,7} {
  \node at (\k+1.5,-0.5) {\k};
  \node at (0.5,-\k-1.5) {\k};
}
% body: (i*j) mod 8
\foreach \i in {0,...,7} \foreach \j in {0,...,7} {
  \pgfmathtruncatemacro{\p}{mod(\i*\j,8)}
  \node at (\j+1.5,-\i-1.5) {\p};
}
\end{tikzpicture}
$$

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](/abstract-algebra/groups-and-symmetry/group-axioms-and-first-examples)
lesson. Its size is counted by Euler's function.

> **Definition (Euler's totient).** $\varphi(n)$ is the number of integers $a$
> with $1 \leq a \leq n$ and $\gcd(a, n) = 1$; equivalently
> $\varphi(n) = |(\mathbb{Z}/n\mathbb{Z})^{\times}|$.

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

| $n$ | $(\mathbb{Z}/n\mathbb{Z})^{\times}$ | $\varphi(n)$ |
| --- | --- | --- |
| $6$ | $\{1, 5\}$ | $2$ |
| $8$ | $\{1, 3, 5, 7\}$ | $4$ |
| $9$ | $\{1, 2, 4, 5, 7, 8\}$ | $6$ |
| $12$ | $\{1, 5, 7, 11\}$ | $4$ |
| $p$ | $\{1, 2, \dots, p-1\}$ | $p - 1$ |

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

[^df-wo]: **Dummit & Foote**, _Abstract Algebra_, §0.2, property (1) — the Well-Ordering of $\mathbb{Z}$: every nonempty subset of $\mathbb{Z}^{+}$ has a minimal element.
[^judson-wo]: **Judson**, _Abstract Algebra: Theory and Applications_, §2.1 — the First and Second (Strong) Principles of Mathematical Induction and their equivalence with the Principle of Well-Ordering (Lemma 2.1, Theorem 2.2).
[^df-div]: **Dummit & Foote**, _Abstract Algebra_, §0.2, property (5) — the Division Algorithm: unique $q, r$ with $a = qb + r$, $0 \leq r < |b|$.
[^judson-div]: **Judson**, _Abstract Algebra: Theory and Applications_, §2.2, Theorem 2.3 — the Division Algorithm, proved by applying the Well-Ordering Principle to $S = \{a - bk : k \in \mathbb{Z},\ a - bk \geq 0\}$, with the uniqueness argument.
[^df-euclid]: **Dummit & Foote**, _Abstract Algebra_, §0.2, property (6) — the Euclidean Algorithm as iterated division, terminating because remainders form a strictly decreasing sequence of nonnegative integers.
[^df-bezout]: **Dummit & Foote**, _Abstract Algebra_, §0.2, property (7) and Exercise 4 — the gcd as a $\mathbb{Z}$-linear combination $ax + by$, and the general solution $x = x_0 + (b/d)t$, $y = y_0 - (a/d)t$.
[^judson-bezout]: **Judson**, _Abstract Algebra: Theory and Applications_, §2.2, Theorem 2.4 and Corollary 2.5 — existence of $r, s$ with $\gcd(a, b) = ar + bs$, via the least positive element of $\{am + bn > 0\}$.
[^df-fta]: **Dummit & Foote**, _Abstract Algebra_, §0.2, properties (8)–(9) — primes, Euclid's lemma ($p \mid ab \Rightarrow p \mid a$ or $p \mid b$), and the Fundamental Theorem of Arithmetic with the gcd/lcm exponent formulas.
[^df-znz]: **Dummit & Foote**, _Abstract Algebra_, §0.3 — $\mathbb{Z}/n\mathbb{Z}$, well-definedness of modular addition and multiplication (Theorem 3), and $(\mathbb{Z}/n\mathbb{Z})^{\times} = \{\overline{a} : \gcd(a, n) = 1\}$ (Proposition 4).
</content>