Abstract Algebra — 00 · Integers, Relations and Modular Arithmetic

Abstract algebra studies structures: a set together with one or more operations that obey a short list of rules. Instead of asking "what is $7 \cdot 13$?", it asks "which facts about multiplication follow from the rules alone, so that they hold for integers, for clock arithmetic, for matrices, for symmetries of a molecule, all at once?". That shift pays off in many places: symmetry (crystallography, chemistry, physics), cryptography (RSA and elliptic-curve systems are group theory in disguise), coding theory (error-correcting codes on every phone and disk are built over finite fields), and the classical question of solving polynomial equations, which Galois settled with groups. This series follows the standard senior undergraduate path of Dummit & Foote, Gallian, Artin and Fraleigh: groups, then rings and fields, then Galois theory. Post 00 lays the ground: the proof methods used throughout, sets and functions, equivalence relations, and the arithmetic of the integers up to modular arithmetic, the Chinese remainder theorem and a small but complete RSA example. Every later post uses $\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$ as its first examples.

Series map: 00 Integers, Relations & Modular Arithmetic (this post) → 01 Groups & Subgroups → 02 Cosets, Lagrange & Quotient Groups → 03 Homomorphisms, Group Actions & Sylow → 04 Rings, Ideals & Fields → 05 Field Extensions & Galois Theory.

---

Learning Outcome

• Read and write the four basic proof patterns: direct, contrapositive, contradiction, induction.
• Decide whether a function is injective, surjective or bijective, and use the fact that bijections are exactly the invertible functions.
• Prove that an equivalence relation on a set is the same thing as a partition of that set.
• State and prove the division algorithm from the well-ordering principle.
• Run the Euclidean algorithm and the extended Euclidean algorithm by hand, and prove Bézout's identity and Euclid's lemma.
• Prove the fundamental theorem of arithmetic (existence and uniqueness).
• Compute in $\mathbb{Z}/n\mathbb{Z}$, find inverses, and decide which classes are units.
• Use Euler's $\varphi$ function, Fermat's little theorem and Euler's theorem to reduce huge powers.
• Solve simultaneous congruences with the Chinese remainder theorem.
• Carry out a toy RSA key generation, encryption and decryption, and explain why decryption works.

---

Chapter 1 — The proof toolkit

Abstract algebra is a proof-based subject. Almost every statement is an implication "if $P$ then $Q$", and there are four standard ways to prove one.

Terminology

• Proposition / theorem / lemma / corollary — a proved statement; a lemma is a helper, a corollary follows quickly from a theorem.
• Definition — fixes the meaning of a word. Definitions are "if and only if" even when written with "if".
• Contrapositive of "$P \Rightarrow Q$" is "not $Q \Rightarrow$ not $P$". It is logically equivalent to the original.
• Converse of "$P \Rightarrow Q$" is "$Q \Rightarrow P$". It is a different statement and may be false.
• Counterexample — one concrete case that shows a universal statement is false.

Direct proof

Assume $P$, reason forward, reach $Q$.

Claim. The sum of two odd integers is even.

Proof. Odd integers can be written $2a+1$ and $2b+1$ with $a, b \in \mathbb{Z}$. Their sum is $2a + 2b + 2 = 2(a+b+1)$, which is even. $\blacksquare$

Proof by contrapositive

Prove "not $Q \Rightarrow$ not $P$" instead.

Claim. If $n^2$ is even, then $n$ is even.

Proof. Contrapositive: if $n$ is odd then $n^2$ is odd. Write $n = 2k+1$; then $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$, which is odd. $\blacksquare$

Proof by contradiction

Assume the statement is false and derive something impossible.

Claim. $\sqrt{2}$ is irrational.

Proof. Suppose $\sqrt{2} = p/q$ with integers $p, q$, $q \neq 0$, and the fraction in lowest terms. Then $p^2 = 2q^2$, so $p^2$ is even, so $p$ is even by the previous claim. Write $p = 2m$: then $4m^2 = 2q^2$, so $q^2 = 2m^2$ is even and $q$ is even. Both $p$ and $q$ are even, contradicting lowest terms. $\blacksquare$

Proof by induction

To prove a statement $S(n)$ for all integers $n \geq n_0$: prove $S(n_0)$ (the base case), then prove $S(k) \Rightarrow S(k+1)$ for every $k \geq n_0$ (the inductive step). In strong induction the inductive step may assume $S(n_0), \dots, S(k)$ all at once.

Claim. For every $n \geq 1$, $1 + 3 + 5 + \dots + (2n-1) = n^2$.

Proof. Base case $n=1$: $1 = 1^2$. Inductive step: if the sum of the first $k$ odd numbers is $k^2$, adding the next one gives $k^2 + (2k+1) = (k+1)^2$. $\blacksquare$

Watch out: proving the converse is not proving the statement. "If $n$ is even then $n^2$ is even" is true, but it does not prove "if $n^2$ is even then $n$ is even"; that needed its own proof above.

---

Chapter 2 — Sets, functions and equivalence relations

Terminology

• $\mathbb{N} = \{0, 1, 2, \dots\}$ (some books start at 1; this series includes 0), $\mathbb{Z}$ the integers, $\mathbb{Q}$ the rationals, $\mathbb{R}$ the reals, $\mathbb{C}$ the complex numbers.
• $A \times B = \{(a, b) : a \in A, b \in B\}$ is the Cartesian product.
• A function $f : A \to B$ assigns to each $a \in A$ exactly one $f(a) \in B$. $A$ is the domain, $B$ the codomain, $f(A)$ the image.
• $f$ is injective (one-to-one) if $f(a_1) = f(a_2)$ implies $a_1 = a_2$.
• $f$ is surjective (onto) if every $b \in B$ equals $f(a)$ for some $a$.
• $f$ is bijective if it is both. A bijection from a set to itself is a permutation of the set.
• A relation on $A$ is a subset $R \subseteq A \times A$; write $a \sim b$ when $(a, b) \in R$.

Functions and inverses

Examples on $\mathbb{Z}$: $f(x) = 2x$ is injective but not surjective (odd numbers are missed). $g(x) = \lfloor x/2 \rfloor$ is surjective but not injective ($g(0) = g(1) = 0$). $h(x) = x + 5$ is bijective with inverse $x \mapsto x - 5$.

Proposition 2.1. A function $f : A \to B$ has an inverse function $g : B \to A$ (with $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$) if and only if $f$ is bijective.

Proof. If $g$ exists: $f(a_1) = f(a_2)$ gives $a_1 = g(f(a_1)) = g(f(a_2)) = a_2$, so $f$ is injective; and any $b$ equals $f(g(b))$, so $f$ is surjective. Conversely, if $f$ is bijective, each $b$ has exactly one preimage; define $g(b)$ to be it. Then both compositions are identities. $\blacksquare$

Proposition 2.2 (pigeonhole). If $A$ is a finite set and $f : A \to A$ is injective, then $f$ is bijective.

Proof. An injective $f$ sends the $\lvert A\rvert$ elements of $A$ to $\lvert A\rvert$ distinct elements of $A$, so the image is all of $A$. $\blacksquare$

This small fact drives the proofs of Fermat's little theorem below and of Cayley's theorem later in the series. It is false for infinite sets: $x \mapsto 2x$ on $\mathbb{Z}$ is injective but not surjective.

Equivalence relations

A relation $\sim$ on $A$ is an equivalence relation if it is

• reflexive: $a \sim a$ for all $a$;
• symmetric: $a \sim b$ implies $b \sim a$;
• transitive: $a \sim b$ and $b \sim c$ imply $a \sim c$.

The equivalence class of $a$ is $[a] = \{x \in A : x \sim a\}$.

Examples: equality on any set; "same birthday" on people; "$a - b$ is divisible by $n$" on $\mathbb{Z}$ (Chapter 5); "same determinant" on $2 \times 2$ matrices. Non-examples: $\leq$ on $\mathbb{R}$ is reflexive and transitive but not symmetric; "$\lvert a - b\rvert \leq 1$" on $\mathbb{R}$ is reflexive and symmetric but not transitive ($0 \sim 1$, $1 \sim 2$, but $0 \not\sim 2$).

A partition of $A$ is a collection of non-empty subsets of $A$ such that every element of $A$ lies in exactly one of them.

Theorem 2.3 (equivalence relations = partitions). If $\sim$ is an equivalence relation on $A$, its equivalence classes form a partition of $A$. Conversely, every partition $\mathcal{P}$ of $A$ comes from exactly one equivalence relation: $a \sim b$ if and only if $a$ and $b$ lie in the same block of $\mathcal{P}$.

Proof. Each class is non-empty and every $a$ lies in a class, because $a \in [a]$ by reflexivity. It remains to show that two classes are either equal or disjoint. Suppose $c \in [a] \cap [b]$, so $c \sim a$ and $c \sim b$. Take any $x \in [a]$: then $x \sim a$, $a \sim c$ (symmetry), $c \sim b$, so $x \sim b$ by transitivity twice, and $x \in [b]$. Hence $[a] \subseteq [b]$, and by the same argument $[b] \subseteq [a]$. So overlapping classes are equal.

Conversely, given a partition, "same block" is reflexive (every element is in a block), symmetric (obvious), and transitive (if $a, b$ share block $P$ and $b, c$ share block $Q$, then $b \in P \cap Q$, so $P = Q$ because blocks are disjoint). Its classes are exactly the blocks. $\blacksquare$

Trick: to show two classes are equal it is enough to find one common element. This "one overlap means equal" step is used again for cosets in post 02, where it gives Lagrange's theorem almost for free.

---

Chapter 3 — Divisibility, gcd and the Euclidean algorithm

Terminology

• $a$ divides $b$, written $a \mid b$, if $b = ak$ for some integer $k$. Every integer divides $0$; $0$ divides only $0$.
• A prime is an integer $p \geq 2$ whose only positive divisors are $1$ and $p$. An integer $n \geq 2$ that is not prime is composite.
• The greatest common divisor $\gcd(a, b)$ of integers not both zero is the largest integer dividing both. Set $\gcd(0, 0) = 0$.
• $a$ and $b$ are coprime (relatively prime) if $\gcd(a, b) = 1$.
• Well-ordering principle: every non-empty set of non-negative integers has a least element. It is equivalent to induction and is taken as an axiom about $\mathbb{N}$.

The division algorithm

Theorem 3.1 (division algorithm). For integers $a$ and $b$ with $b > 0$ there are unique integers $q, r$ with

$$a = qb + r, \qquad 0 \leq r < b.$$

Proof. Existence: let $S = \{a - kb : k \in \mathbb{Z}, \ a - kb \geq 0\}$. $S$ is non-empty (take $k = -\lvert a\rvert$; then $a - kb = a + \lvert a\rvert b \geq a + \lvert a\rvert \geq 0$). By well-ordering $S$ has a least element $r = a - qb \geq 0$. If $r \geq b$, then $r - b = a - (q+1)b$ is a smaller element of $S$, a contradiction. So $0 \leq r < b$.

Uniqueness: if $qb + r = q'b + r'$ with both remainders in $[0, b)$, then $b(q - q') = r' - r$ and $\lvert r' - r\rvert < b$. The only multiple of $b$ strictly between $-b$ and $b$ is $0$, so $r = r'$ and $q = q'$. $\blacksquare$

For negative $a$ the remainder is still non-negative: $-17 = (-4) \cdot 5 + 3$, not $(-3) \cdot 5 - 2$.

Common pitfall: in many programming languages -17 % 5 returns -2 (C, Java, JavaScript) while Python returns 3. Mathematics always uses $0 \leq r < b$.

The Euclidean algorithm

Lemma 3.2. If $a = qb + r$, then $\gcd(a, b) = \gcd(b, r)$.

Proof. Any common divisor of $a$ and $b$ divides $r = a - qb$; any common divisor of $b$ and $r$ divides $a = qb + r$. The two pairs have the same common divisors, so the same greatest one. $\blacksquare$

Repeating the division algorithm, the remainders strictly decrease and so reach $0$; the last non-zero remainder is the gcd. For $\gcd(240, 46)$:

$$\begin{aligned} 240 &= 5 \cdot 46 + 10 \\ 46 &= 4 \cdot 10 + 6 \\ 10 &= 1 \cdot 6 + 4 \\ 6 &= 1 \cdot 4 + 2 \\ 4 &= 2 \cdot 2 + 0 \end{aligned}$$

So $\gcd(240, 46) = 2$. The number of steps is small: it grows like the number of digits (Lamé's theorem bounds it by five times the number of decimal digits of the smaller number).

Bézout's identity and the extended algorithm

Theorem 3.3 (Bézout). For integers $a, b$ not both zero, there are integers $x, y$ with $ax + by = \gcd(a, b)$. Moreover $\gcd(a, b)$ is the smallest positive integer of the form $ax + by$.

Proof. Let $S = \{ax + by : x, y \in \mathbb{Z}\} \cap \{1, 2, 3, \dots\}$. It is non-empty (it contains $a^2 + b^2 > 0$), so it has a least element $d = ax_0 + by_0$. Divide: $a = qd + r$ with $0 \leq r < d$. Then $r = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)$ has the same form, so by minimality $r = 0$ and $d \mid a$. Likewise $d \mid b$. Any common divisor $c$ of $a, b$ divides $ax_0 + by_0 = d$, so $c \leq d$. Hence $d = \gcd(a, b)$. $\blacksquare$

The proof shows $x, y$ exist but does not find them. The extended Euclidean algorithm does: keep, next to every remainder $r_i$, integers $s_i, t_i$ with $r_i = 240 s_i + 46 t_i$. Start with $r_0 = 240 = 240 \cdot 1 + 46 \cdot 0$ and $r_1 = 46 = 240 \cdot 0 + 46 \cdot 1$; each new row is "row two above minus $q$ times row above".

$i$	$r_i$	$q_i$	$s_i$	$t_i$	check $240 s_i + 46 t_i$
0	240	—	1	0	240
1	46	—	0	1	46
2	10	5	1	−5	240 − 230 = 10
3	6	4	−4	21	−960 + 966 = 6
4	4	1	5	−26	1200 − 1196 = 4
5	2	1	−9	47	−2160 + 2162 = 2
6	0	2	—	—	stop

So $2 = 240 \cdot (-9) + 46 \cdot 47$. The same answer comes from back-substitution, reading the divisions from the bottom up: $2 = 6 - 4 = 6 - (10 - 6) = 2 \cdot 6 - 10 = 2(46 - 4 \cdot 10) - 10 = 2 \cdot 46 - 9 \cdot 10 = 2 \cdot 46 - 9(240 - 5 \cdot 46) = 47 \cdot 46 - 9 \cdot 240$.

Trick: the $x, y$ are not unique: $(x + 23k, \ y - 120k)$ works for every integer $k$, because $240 \cdot 23 = 46 \cdot 120$. Add a check column like the one above; one wrong sign early ruins every later row.

Euclid's lemma

Theorem 3.4 (Euclid's lemma). If $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$. In particular, if a prime $p$ divides $bc$, then $p \mid b$ or $p \mid c$.

Proof. By Bézout, $ax + by = 1$ for some $x, y$. Multiply by $c$: $c = acx + bcy$. The number $a$ divides $acx$ and divides $bcy$ (because $a \mid bc$), so $a \mid c$. For the prime case: if $p \nmid b$ then $\gcd(p, b) = 1$ (the only positive divisors of $p$ are $1$ and $p$), so $p \mid c$. $\blacksquare$

Watch out: the prime hypothesis matters. $6 \mid 4 \cdot 9 = 36$ but $6 \nmid 4$ and $6 \nmid 9$.

---

Chapter 4 — The fundamental theorem of arithmetic

Theorem 4.1 (fundamental theorem of arithmetic). Every integer $n \geq 2$ can be written as a product of primes $n = p_1 p_2 \cdots p_k$, and this factorisation is unique up to the order of the factors.

Proof. Existence, by strong induction on $n$. If $n$ is prime, it is its own factorisation. Otherwise $n = ab$ with $2 \leq a, b < n$; by the induction hypothesis both $a$ and $b$ are products of primes, so $n$ is too.

Uniqueness, by induction on $n$. Suppose $n = p_1 \cdots p_k = q_1 \cdots q_l$ with all $p_i, q_j$ prime. Then $p_1$ divides $q_1 \cdots q_l$, so by Euclid's lemma (applied repeatedly) $p_1 \mid q_j$ for some $j$. Since $q_j$ is prime and $p_1 \geq 2$, $p_1 = q_j$. Reorder so that $j = 1$ and cancel: $p_2 \cdots p_k = q_2 \cdots q_l$ is a smaller number (or both sides are empty products equal to $1$), and by induction the remaining primes agree up to order. $\blacksquare$

Grouping equal primes gives the canonical form $n = p_1^{e_1} \cdots p_r^{e_r}$ with $p_1 < \dots < p_r$. Examples: $360 = 2^3 \cdot 3^2 \cdot 5$, $1001 = 7 \cdot 11 \cdot 13$, $2026 = 2 \cdot 1013$.

Corollary 4.2 (Euclid). There are infinitely many primes.

Proof. Given primes $p_1, \dots, p_k$, the number $N = p_1 \cdots p_k + 1$ has a prime factor $p$ by Theorem 4.1. If $p$ were some $p_i$, then $p$ would divide $N - p_1 \cdots p_k = 1$, which is impossible. So no finite list contains every prime. $\blacksquare$

Uniqueness is not automatic. In the set $\{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}$, $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ gives two genuinely different factorisations into elements that cannot be split further. Explaining when unique factorisation holds is one of the main themes of ring theory (post 04).

---

Chapter 5 — Congruences and $\mathbb{Z}/n\mathbb{Z}$

Terminology

• Fix an integer $n \geq 1$, the modulus. $a$ is congruent to $b$ modulo $n$, written $a \equiv b \pmod{n}$, if $n \mid a - b$.
• The class of $a$ is $[a]_n = \{a + kn : k \in \mathbb{Z}\}$, also written $\bar{a}$ or just $a$ when the modulus is clear.
• $\mathbb{Z}/n\mathbb{Z}$ (also written $\mathbb{Z}_n$) is the set of the $n$ classes $[0], [1], \dots, [n-1]$.
• A class $[a]$ is a unit if there is $[b]$ with $[a][b] = [1]$. The units form $(\mathbb{Z}/n\mathbb{Z})^\times$, also written $U(n)$.
• A non-zero class $[a]$ is a zero divisor if $[a][b] = [0]$ for some non-zero $[b]$.

Congruence mod $n$ is an equivalence relation: $n \mid 0$ (reflexive); $n \mid a - b$ implies $n \mid b - a$ (symmetric); $n \mid a - b$ and $n \mid b - c$ imply $n \mid a - c$ (transitive). By Theorem 2.3 its classes partition $\mathbb{Z}$, and by the division algorithm each class contains exactly one of $0, 1, \dots, n-1$, so there are exactly $n$ classes.

Arithmetic on classes

Define $[a] + [b] = [a + b]$ and $[a] \cdot [b] = [ab]$.

Proposition 5.1. These operations are well defined: the result does not depend on which representatives are chosen.

Proof. Suppose $a \equiv a'$ and $b \equiv b'$, say $a' = a + kn$ and $b' = b + ln$. Then $a' + b' = a + b + (k + l)n \equiv a + b$ and $a'b' = ab + (al + bk + kln)n \equiv ab$. $\blacksquare$

"Well defined" is the central worry whenever an operation is defined on classes through representatives. The same check, done for cosets, is what forces the definition of a normal subgroup in post 02.

In practice: reduce early and often. For example $3^{100} \bmod 7$: $3^6 \equiv 1 \pmod 7$ (checked below), and $100 = 6 \cdot 16 + 4$, so $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Units and zero divisors

In $\mathbb{Z}/12\mathbb{Z}$: $[3][4] = [12] = [0]$, so $[3]$ and $[4]$ are zero divisors. On the other hand $[5][5] = [25] = [1]$, $[7][7] = [49] = [1]$ and $[11][11] = [121] = [1]$. The units are exactly $[1], [5], [7], [11]$, the classes coprime to $12$, and each of them is its own inverse.

Theorem 5.2. $[a]$ is a unit in $\mathbb{Z}/n\mathbb{Z}$ if and only if $\gcd(a, n) = 1$. If $\gcd(a, n) = d > 1$ and $n \nmid a$, then $[a]$ is a zero divisor.

Proof. If $\gcd(a, n) = 1$, Bézout gives $ax + ny = 1$, so $ax \equiv 1$ and $[x]$ is the inverse. Conversely if $ab \equiv 1$, then $ab - 1 = kn$, so $ab - kn = 1$ and every common divisor of $a$ and $n$ divides $1$. For the last claim: $a \cdot (n/d) = (a/d) \cdot n \equiv 0$, and $[n/d] \neq [0]$ because $0 < n/d < n$. $\blacksquare$

Corollary 5.3. $\mathbb{Z}/n\mathbb{Z}$ has every non-zero class invertible if and only if $n$ is prime.

Theorem 5.2 is also an algorithm: the inverse is the Bézout coefficient. To invert $17$ modulo $43$: $43 = 2 \cdot 17 + 9$, $17 = 1 \cdot 9 + 8$, $9 = 1 \cdot 8 + 1$. Back-substitute: $1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17$. So $17^{-1} \equiv -5 \equiv 38 \pmod{43}$. Check: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$.

Linear congruences

Theorem 5.4. The congruence $ax \equiv b \pmod n$ has a solution if and only if $d = \gcd(a, n)$ divides $b$. In that case it has exactly $d$ solutions modulo $n$.

Proof sketch. A solution means $ax - ny = b$ for some $y$, and by Bézout the values of $ax - ny$ are exactly the multiples of $d$. If $d \mid b$, divide through: $(a/d)x \equiv b/d \pmod{n/d}$, and $a/d$ is a unit mod $n/d$, so $x$ is unique mod $n/d$. That single class mod $n/d$ splits into $d$ classes mod $n$. $\blacksquare$

Example: $14x \equiv 6 \pmod{20}$. Here $\gcd(14, 20) = 2$ divides $6$. Divide by 2: $7x \equiv 3 \pmod{10}$. Since $7 \cdot 3 = 21 \equiv 1$, $7^{-1} \equiv 3 \pmod{10}$, so $x \equiv 9 \pmod{10}$, giving $x \equiv 9$ or $19 \pmod{20}$. Check: $14 \cdot 9 = 126 = 6 \cdot 20 + 6$ and $14 \cdot 19 = 266 = 13 \cdot 20 + 6$.

Common pitfall: you may not "divide both sides" of a congruence by a number that is not a unit. $2 \cdot 3 \equiv 2 \cdot 9 \pmod{12}$, but $3 \not\equiv 9 \pmod{12}$. Division by $a$ modulo $n$ is multiplication by $a^{-1}$, which exists only when $\gcd(a, n) = 1$; otherwise the modulus must be divided too, as above.

---

Chapter 6 — Euler's phi, Fermat and Euler

Euler's phi function

$\varphi(n)$ is the number of integers in $\{1, \dots, n\}$ coprime to $n$; by Theorem 5.2 it is the number of units, $\varphi(n) = \lvert(\mathbb{Z}/n\mathbb{Z})^\times\rvert$.

• For a prime $p$: $\varphi(p) = p - 1$.
• For a prime power: $\varphi(p^k) = p^k - p^{k-1}$, because the numbers in $\{1, \dots, p^k\}$ not coprime to $p^k$ are exactly the $p^{k-1}$ multiples of $p$.
• Multiplicative: if $\gcd(m, n) = 1$ then $\varphi(mn) = \varphi(m)\varphi(n)$. This follows from the Chinese remainder theorem (Chapter 7): $a$ is coprime to $mn$ exactly when it is coprime to both $m$ and $n$, and the CRT bijection matches such $a$ with pairs of units.

Together these give, for $n = p_1^{e_1} \cdots p_r^{e_r}$,

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$

Examples: $\varphi(12) = 12 \cdot \tfrac12 \cdot \tfrac23 = 4$ (the units $1, 5, 7, 11$); $\varphi(36) = 36 \cdot \tfrac12 \cdot \tfrac23 = 12$; $\varphi(100) = 100 \cdot \tfrac12 \cdot \tfrac45 = 40$; $\varphi(35) = \varphi(5)\varphi(7) = 4 \cdot 6 = 24$.

Fermat's little theorem

Theorem 6.1 (Fermat's little theorem). If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. Consequently $a^p \equiv a \pmod p$ for every integer $a$.

Proof. Consider the map $x \mapsto ax$ on the set $R = \{[1], [2], \dots, [p-1]\}$ of non-zero classes mod $p$. It lands in $R$ (a product of two units is a unit, so never $[0]$) and is injective, because $ax \equiv ay$ implies $x \equiv y$ after multiplying by $a^{-1}$. By the pigeonhole Proposition 2.2 it is a bijection, so it just reorders $R$. Multiply all elements of $R$ both ways:

$$(a \cdot 1)(a \cdot 2) \cdots (a \cdot (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod p,$$

that is $a^{p-1} (p-1)! \equiv (p-1)! \pmod p$. Every factor of $(p-1)!$ is a unit, so $(p-1)!$ is a unit and can be cancelled: $a^{p-1} \equiv 1$. For the second statement multiply by $a$; if $p \mid a$ both sides are $0$. $\blacksquare$

Check with $p = 7$, $a = 3$: multiplying $1, 2, 3, 4, 5, 6$ by 3 gives $3, 6, 2, 5, 1, 4$ modulo 7, the same six classes in a new order, and $3^6 = 729 = 104 \cdot 7 + 1$.

Euler's theorem

Theorem 6.2 (Euler). If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod n$.

Proof. Repeat the proof above with the set $U$ of the $\varphi(n)$ units mod $n$ instead of $R$: $x \mapsto ax$ permutes $U$, so $a^{\varphi(n)} \prod_{u \in U} u \equiv \prod_{u \in U} u$, and the product of units is a unit, so it cancels. $\blacksquare$

Fermat is the case $n = p$. Post 02 re-proves both in one line from Lagrange's theorem, because $(\mathbb{Z}/n\mathbb{Z})^\times$ is a group of order $\varphi(n)$ and the order of an element divides the order of the group.

Example: the last digit of $7^{222}$. $\varphi(10) = 4$ and $\gcd(7, 10) = 1$, so $7^4 \equiv 1 \pmod{10}$. Since $222 = 4 \cdot 55 + 2$, $7^{222} \equiv 7^2 = 49 \equiv 9$. The last digit is 9.

Watch out: Euler's theorem needs $\gcd(a, n) = 1$. $2^{\varphi(4)} = 2^2 = 4 \equiv 0 \pmod 4$, not 1. Also, $\varphi(n)$ is an exponent that always works, not always the smallest one: modulo 12, every unit already satisfies $u^2 \equiv 1$ although $\varphi(12) = 4$.

---

Chapter 7 — The Chinese remainder theorem

Theorem 7.1 (Chinese remainder theorem). Let $n_1, \dots, n_k$ be pairwise coprime positive integers and $N = n_1 \cdots n_k$. For any integers $a_1, \dots, a_k$ the system

$$x \equiv a_1 \pmod{n_1}, \quad \dots, \quad x \equiv a_k \pmod{n_k}$$

has a solution, and any two solutions are congruent modulo $N$.

Proof. Existence: put $N_i = N / n_i$. Since $n_i$ is coprime to every other $n_j$, it is coprime to $N_i$, so there is $M_i$ with $N_i M_i \equiv 1 \pmod{n_i}$. Let $x = \sum_i a_i N_i M_i$. Modulo $n_j$, every term with $i \neq j$ vanishes (because $n_j \mid N_i$), and the $j$-th term is $a_j \cdot 1$. Uniqueness: if $x, x'$ both work, each $n_i$ divides $x - x'$; the $n_i$ are pairwise coprime, so (by Euclid's lemma, repeatedly) their product $N$ divides $x - x'$. $\blacksquare$

Worked example (Sunzi's classic puzzle). Find $x$ with $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. Here $N = 105$.

$i$	$n_i$	$a_i$	$N_i = N/n_i$	$N_i \bmod n_i$	$M_i$	$a_i N_i M_i$
1	3	2	35	2	2	140
2	5	3	21	1	1	63
3	7	2	15	1	1	30

Sum: $140 + 63 + 30 = 233 \equiv 23 \pmod{105}$. Check: $23 = 7 \cdot 3 + 2$, $23 = 4 \cdot 5 + 3$, $23 = 3 \cdot 7 + 2$.

In structural language, the theorem says that the map $\mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \dots \times \mathbb{Z}/n_k\mathbb{Z}$, $[x] \mapsto ([x]_{n_1}, \dots, [x]_{n_k})$, is a bijection that respects addition and multiplication. Both sides have $N$ elements, so it is enough to know the map is injective, which is the uniqueness part. Post 01 meets the additive version as "$\mathbb{Z}/6\mathbb{Z}$ is the same group as $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$", and post 04 the ring version.

Common pitfall: the moduli must be pairwise coprime. The system $x \equiv 0 \pmod 4$, $x \equiv 1 \pmod 6$ has no solution: the first says $x$ is even, the second says $x$ is odd.

---

Chapter 8 — A toy RSA

RSA (Rivest, Shamir and Adleman, 1978) is Euler's theorem put to work. The numbers below are tiny so that every step can be checked by hand; real keys use primes of about 1024 bits or more and a padding scheme, and textbook RSA as shown here is not secure.

Key generation.

1. Pick primes $p = 11$, $q = 17$. The modulus is $n = pq = 187$.
2. $\varphi(n) = (p-1)(q-1) = 10 \cdot 16 = 160$.
3. Pick a public exponent $e$ coprime to 160: $e = 7$.
4. The private exponent is $d = e^{-1} \bmod \varphi(n)$: since $7 \cdot 23 = 161 = 160 + 1$, $d = 23$.

Public key $(n, e) = (187, 7)$; private key $d = 23$.

Encryption of the message $m = 88$ (any integer with $0 \leq m < n$): $c = m^e \bmod n$, computed by repeated squaring so that no number exceeds $186^2$:

$$\begin{aligned} 88^2 &= 7744 \equiv 77 \pmod{187} \\ 88^4 &\equiv 77^2 = 5929 \equiv 132 \\ 88^7 &= 88^4 \cdot 88^2 \cdot 88 \equiv 132 \cdot 77 \cdot 88 \equiv 66 \cdot 88 = 5808 \equiv 11 \end{aligned}$$

So the ciphertext is $c = 11$.

Decryption: $c^d = 11^{23} \bmod 187$. Write $23 = 16 + 4 + 2 + 1$ and square repeatedly: $11^2 = 121$, $11^4 \equiv 121^2 = 14641 \equiv 55$, $11^8 \equiv 55^2 = 3025 \equiv 33$, $11^{16} \equiv 33^2 = 1089 \equiv 154$. Then

$$11^{23} \equiv 154 \cdot 55 \cdot 121 \cdot 11 \equiv 55 \cdot 121 \cdot 11 \equiv 110 \cdot 11 = 1210 \equiv 88 \pmod{187}.$$

The original message comes back.

Why it works. $ed = 1 + k\varphi(n)$ for some $k \geq 0$. If $\gcd(m, n) = 1$, Euler gives $m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m \pmod n$. (If $m$ shares a factor with $n$, the result still holds: check it modulo $p$ and modulo $q$ separately with Fermat, then combine with the CRT.)

Why it is believed hard to break. Anyone who knows $\varphi(n)$ can compute $d$ with the extended Euclidean algorithm, and $\varphi(n)$ is easy from $p$ and $q$. So the security rests on the difficulty of factoring $n$; no fast classical factoring algorithm is known.

---

Practice Exercises

1. Prove by induction that $6 \mid n^3 - n$ for every integer $n \geq 0$.

Solution

Base: $0^3 - 0 = 0$. Step: $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1)$. The first term is divisible by 6 by hypothesis; $k(k+1)$ is a product of consecutive integers, hence even, so $3k(k+1)$ is divisible by 6. (A direct proof also works: $n^3 - n = (n-1)n(n+1)$ is a product of three consecutive integers, so it is divisible by 2 and by 3.)

2. On $\mathbb{R}^2$ define $(x_1, y_1) \sim (x_2, y_2)$ if $x_1^2 + y_1^2 = x_2^2 + y_2^2$. Show this is an equivalence relation and describe the partition.

Solution

It is "$f(p_1) = f(p_2)$" for the function $f(x, y) = x^2 + y^2$, and any relation of that form inherits reflexivity, symmetry and transitivity from equality. The classes are the circles centred at the origin, plus the single point $(0,0)$.

3. Use the extended Euclidean algorithm to find $\gcd(252, 198)$ and integers $x, y$ with $252x + 198y = \gcd(252, 198)$.

Solution

$252 = 1 \cdot 198 + 54$, $198 = 3 \cdot 54 + 36$, $54 = 1 \cdot 36 + 18$, $36 = 2 \cdot 18$. So the gcd is 18. Back-substitute: $18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198$. Check: $1008 - 990 = 18$.

4. Find all solutions of $14x \equiv 6 \pmod{20}$ by the method of Theorem 5.4, and explain why $14x \equiv 5 \pmod{20}$ has none.

Solution

As in Chapter 5: $x \equiv 9$ or $19 \pmod{20}$. For the second congruence, $\gcd(14, 20) = 2$ does not divide 5: the left side $14x - 20y$ is always even, the right side is odd.

5. Compute $2^{1000} \bmod 13$ and the last two digits of $3^{2026}$.

Solution

By Fermat $2^{12} \equiv 1 \pmod{13}$; $1000 = 12 \cdot 83 + 4$, so $2^{1000} \equiv 2^4 = 16 \equiv 3$. For the last two digits work mod 100: $\varphi(100) = 40$ and $\gcd(3, 100) = 1$, so $3^{40} \equiv 1$; $2026 = 40 \cdot 50 + 26$, so $3^{2026} \equiv 3^{26}$. Now $3^5 = 243 \equiv 43$, $3^{10} \equiv 43^2 = 1849 \equiv 49$, $3^{20} \equiv 49^2 = 2401 \equiv 1$. (The order of 3 mod 100 is actually 20, a divisor of 40.) So $3^{26} \equiv 3^{6} = 729 \equiv 29$. The last two digits are 29.

6. Solve $x \equiv 3 \pmod 4$, $x \equiv 4 \pmod 9$.

Solution

$N = 36$. $N_1 = 9 \equiv 1 \pmod 4$, so $M_1 = 1$; $N_2 = 4$ and $4 \cdot 7 = 28 \equiv 1 \pmod 9$, so $M_2 = 7$. Then $x = 3 \cdot 9 \cdot 1 + 4 \cdot 4 \cdot 7 = 27 + 112 = 139 \equiv 31 \pmod{36}$. Check: $31 = 7 \cdot 4 + 3$ and $31 = 3 \cdot 9 + 4$.

7. With $p = 5$, $q = 11$ and $e = 3$, find $n$, $\varphi(n)$ and $d$; encrypt $m = 7$ and decrypt the result.

Solution

$n = 55$, $\varphi(n) = 4 \cdot 10 = 40$, $d = 27$ because $3 \cdot 27 = 81 = 2 \cdot 40 + 1$. Encrypt: $7^3 = 343 = 6 \cdot 55 + 13$, so $c = 13$. Decrypt: $13^2 = 169 \equiv 4$, $13^4 \equiv 16$, $13^8 \equiv 256 \equiv 36$, $13^{16} \equiv 36^2 = 1296 \equiv 31$. With $27 = 16 + 8 + 2 + 1$: $31 \cdot 36 = 1116 \equiv 16$, $16 \cdot 4 = 64 \equiv 9$, $9 \cdot 13 = 117 \equiv 7$. The message 7 comes back.

---

Cheat-sheet

Idea	Statement or method
Equivalence relation	reflexive, symmetric, transitive; classes partition the set
Division algorithm	$a = qb + r$, $0 \leq r < b$, unique
Euclidean algorithm	$\gcd(a, b) = \gcd(b, a \bmod b)$; last non-zero remainder
Bézout	$ax + by = \gcd(a, b)$; gcd is the least positive such value
Extended Euclid	new row = row two above minus $q$ times row above
Euclid's lemma	$p \mid bc \Rightarrow p \mid b$ or $p \mid c$
FTA	unique factorisation into primes, up to order
$\mathbb{Z}/n\mathbb{Z}$	$n$ classes; $+$ and $\cdot$ well defined
Unit test	$[a]$ invertible iff $\gcd(a, n) = 1$; inverse from Bézout
$ax \equiv b$	solvable iff $\gcd(a,n) \mid b$; then $\gcd(a,n)$ solutions
Euler phi	$\varphi(n) = n \prod (1 - 1/p)$ over primes $p \mid n$
Fermat	$a^{p-1} \equiv 1 \pmod p$ if $p \nmid a$
Euler	$a^{\varphi(n)} \equiv 1 \pmod n$ if $\gcd(a, n) = 1$
CRT	pairwise coprime moduli: unique solution mod $N = \prod n_i$
RSA	$n = pq$, $ed \equiv 1 \pmod{\varphi(n)}$, $c = m^e$, $m = c^d$ mod $n$

---

What's next

Post 01 takes the pattern seen here (a set, one operation, an identity, inverses) and turns it into the definition of a group. $\mathbb{Z}$ under addition, $\mathbb{Z}/n\mathbb{Z}$ under addition and $(\mathbb{Z}/n\mathbb{Z})^\times$ under multiplication become the first examples, joined by permutations, symmetries of polygons, invertible matrices and the quaternions. The division algorithm reappears in the proof that every subgroup of a cyclic group is cyclic, and $\gcd$ returns in the formula $n / \gcd(k, n)$ for the order of $k$ in $\mathbb{Z}/n\mathbb{Z}$.

---

References

• David S. Dummit and Richard M. Foote, Abstract Algebra, 3rd edition, Wiley, 2004 — Chapter 0 (preliminaries: relations, integers, $\mathbb{Z}/n\mathbb{Z}$).
• Joseph A. Gallian, Contemporary Abstract Algebra, 10th edition, CRC Press, 2021 — Chapter 0 (preliminaries, including the RSA-style applications).
• Michael Artin, Algebra, 2nd edition, Pearson, 2011.
• John B. Fraleigh, A First Course in Abstract Algebra, 7th edition, Addison-Wesley, 2003 — Section 0 (sets and relations).
• Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991 — divisibility, congruences, the CRT.
• Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), judsonbooks.org — chapters on the integers and on RSA.
• MIT OpenCourseWare, 18.701 Algebra I (Fall 2010) — lecture notes and problem sets following Artin.
• R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21(2), 1978, pp. 120–126.

Note: this post is in progress. Planned additions: a proof that well-ordering and induction are equivalent, the CRT proof of multiplicativity of $\varphi$ written out in full, Wilson's theorem, and a short section on fast modular exponentiation cost (number of multiplications versus bit length).

---