Lecture 12 — Modular Arithmetic and the Euclidean Algorithm
Pre-work: Video 015 (The Euclidean Algorithm). See gcd-lcm-and-euclidean-algorithm for the reference definitions, worked runs of the algorithm and the gcd/lcm proofs.
Learning goals
- Continue to gain fluency in applying modular arithmetic.
- Understand the definitions of \(\gcd(a,b)\) and \(\operatorname{lcm}(a,b)\) for integers \(a\) and \(b\).
- Be able to apply the Euclidean algorithm to find the greatest common divisor of two integers.
Student questions and comments
Is \(\gcd(a,b) = \gcd(b,a)\)? Yes.
How do you do gcd and lcm with a mix of positive and negative integers? Covered below — take absolute values.
Where are gcd, lcm and the Euclidean algorithm used? Used all the time in arithmetic (adding fractions, etc.); used to determine if certain types of equations have solutions; applications in cryptography.
Recap on mod
For \(n, d \in \mathbb{Z}\), \(d > 0\): \(n \bmod d = r\) indicates the remainder when \(n\) is divided by \(d\) is \(r\), with \(0 \leq r < d\). For \(m, n, d \in \mathbb{Z}\), \(d > 0\): \(m \equiv n \pmod d\) indicates \(m\) and \(n\) have the same remainder when divided by \(d\) — equivalently \(d \mid (m-n)\). See modular-arithmetic.
Poll question 1
If \(m \in \mathbb{Z}\) and \(m \bmod 6 = 4\), what is the remainder when \(35m\) is divided by 6?
C. 2. Since \(35 \bmod 6 = 5\) and \(m \equiv 4\), we get \(35m \equiv 5 \cdot 4 \equiv 20 \equiv 2 \pmod 6\).
Poll question 2
If \(m \in \mathbb{Z}\) and \(m \bmod 6 = 4\), what is the remainder when \(3m^2 + 2m + 1\) is divided by 6?
D. 3. \(3m^2 + 2m + 1 \equiv 3(4)^2 + 2(4) + 1 \equiv 3(16) + 8 + 1 \equiv 48 + 9 \pmod 6\), and \(48 \equiv 0 \pmod 6\) (since \(6 \mid 48\)), so this is \(\equiv 9 \equiv 3 \pmod 6\).
\(\gcd(a,b)\)
Definition: for integers \(a\) and \(b\), not both zero, the greatest common divisor of \(a\) and \(b\), denoted \(\gcd(a,b)\), is the integer \(d\) for which:
- \(d \mid a\) and \(d \mid b\) — \(d\) is a divisor of both \(a\) and \(b\); and
- \(\forall c \in \mathbb{Z}\), if \(c \mid a\) and \(c \mid b\) then \(c \leq d\) — every other divisor of both \(a\) and \(b\) is less than \(d\).
(Also written \(\operatorname{hcf}(a,b)\).) The order of \(a\) and \(b\) does not matter.
What if one, or both, of \(a\) and \(b\) are negative? The divisors of 15 are \(1, 3, 5, 15, -1, -3, -5, -15\) — and these are also the divisors of \(-15\). The divisors of an integer \(a\) are the same as the divisors of \(-a\). Thus \(\gcd(-15, 36) = \gcd(15,36)\), and in general
\[\gcd(a,b) = \gcd(|a|, |b|)\]
Note that \(\gcd(0,b) = b\) for all positive integers \(b\) — this is the base case the algorithm below terminates on.
\(\operatorname{lcm}(a,b)\)
Definition: for non-zero integers \(a\) and \(b\), the lowest (least) common multiple of \(a\) and \(b\), denoted \(\operatorname{lcm}(a,b)\), is the smallest integer \(n\) for which:
- \(n > 0\) — every other positive multiple of both \(a\) and \(b\) is greater than \(n\); and
- \(a \mid n\) and \(b \mid n\) — \(n\) is a multiple of both \(a\) and \(b\).
Order does not matter. The multiples of 5 are \(\dots, -10, -5, 0, 5, 10, 15, \dots\) — the same as the multiples of \(-5\). So \(\operatorname{lcm}(-5, 36) = \operatorname{lcm}(5, 36)\), and in general
\[\operatorname{lcm}(a,b) = \operatorname{lcm}(|a|, |b|)\]
Relationship between gcd and lcm
Use the unique prime factorisation of each integer (see divisibility-and-factorisation) — step 1: factorise; step 2: take minimum exponents for gcd, maximum for lcm.
\[30 = 2 \cdot 3 \cdot 5 \qquad 72 = 2^3 \cdot 3^2\] \[\gcd(30,72) = 2 \cdot 3 = 6 \qquad \operatorname{lcm}(30,72) = 2^3 \cdot 3^2 \cdot 5 = 360\]
Lemma: if \(a, b \in \mathbb{Z}^+\), then \(\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab\).
Checking: \(\gcd(30,72) \cdot \operatorname{lcm}(30,72) = 6 \cdot 360 = 30 \cdot 72\), since \((2 \cdot 3)(2^3 \cdot 3^2 \cdot 5) = (2 \cdot 3 \cdot 5)(2^3 \cdot 3^2)\).
More generally, for non-zero integers \(a\) and \(b\): \(\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |ab|\).
Activity 1
\(\gcd(63, -105)\) and \(\operatorname{lcm}(63, -105)\):
- Step 1: \(63 = 3^2 \cdot 7\) and \(-105 = -3 \cdot 5 \cdot 7\).
- Step 2: \(\gcd(63,-105) = 3 \cdot 7 = 21\); \(\operatorname{lcm}(63,-105) = 3^2 \cdot 5 \cdot 7 = 315\).
Activity 2
Let \(p\) and \(q\) be distinct primes (\(p \neq q\)). Then \(\gcd(p,q) = 1\) and \(\operatorname{lcm}(p,q) = pq\).
The Euclidean algorithm
To determine \(\gcd(a,b)\) for \(a, b \in \mathbb{Z}^+\), based on the fact:
if \(a, b \in \mathbb{Z}\) are not both zero and \(q, r \in \mathbb{Z}\) satisfy \(a = bq + r\), then \(\gcd(a,b) = \gcd(b,r)\).
The proof of this fact is basically showing that every divisor of \(a\) and \(b\) is also a divisor of \(b\) and \(r\), and vice versa:
- Suppose \(c \mid a\) and \(c \mid b\). Then \(c \mid (a - bq)\) and hence \(c \mid r\).
- Suppose \(d \mid b\) and \(d \mid r\). Then \(d \mid (bq + r)\) and hence \(d \mid a\).
Divide the big by the small, then repeat on (small, remainder).
Example: \(\gcd(1232, 5859)\).
| Division | Consequence |
|---|---|
| \(5859 = 1232 \cdot 4 + 931\) | \(\gcd(5859, 1232) = \gcd(1232, 931)\) |
| \(1232 = 931 \cdot 1 + 301\) | \(\gcd(1232, 931) = \gcd(931, 301)\) |
| \(931 = 301 \cdot 3 + 28\) | \(\gcd(931, 301) = \gcd(301, 28)\) |
| \(301 = 28 \cdot 10 + 21\) | \(\gcd(301, 28) = \gcd(28, 21)\) |
| \(28 = 21 \cdot 1 + 7\) | \(\gcd(28, 21) = \gcd(21, 7)\) |
| \(21 = 7 \cdot 3 + 0\) | \(\gcd(21, 7) = \gcd(7, 0) = 7\) |
Therefore \(\gcd(5859, 1232) = 7\).
Activity 3
Use the Euclidean Algorithm to determine \(\gcd(4131, 2431)\).
| \(a\) | \(=\) | \(b \times q\) | \(+ \; r\) |
|---|---|---|---|
| 4131 | \(=\) | \(2431 \times 1\) | \(+ \; 1700\) |
| 2431 | \(=\) | \(1700 \times 1\) | \(+ \; 731\) |
| 1700 | \(=\) | \(731 \times 2\) | \(+ \; 238\) |
| 731 | \(=\) | \(238 \times 3\) | \(+ \; 17\) |
| 238 | \(=\) | \(17 \times 14\) | \(+ \; 0\) |
\[\gcd(4131, 2431) = \cdots = \gcd(238, 17) = \gcd(17, 0) = \mathbf{17}\]
Activity 4 — an “if and only if” proof
Prove that for all positive integers \(a\) and \(b\), \(a \mid b\) if and only if \(\operatorname{lcm}(a,b) = b\).
Not a counterexample; a direct proof of a biconditional.
Method 1: prove each direction separately — the recommended method.
(\(\Rightarrow\)) Suppose \(a, b \in \mathbb{Z}^+\) and suppose \(a \mid b\). Then \(\exists k \in \mathbb{Z}\) such that \(b = ka\). So \(\operatorname{lcm}(a,b) = \operatorname{lcm}(a, ka)\). Since \(a \mid ka\) and \(ka \mid ka\), and no smaller \(n > 0\) has \(ka \mid n\), we have \(\operatorname{lcm}(a, ka) = ka\). Therefore \(\operatorname{lcm}(a,b) = b\) (since \(b = ka\)).
(\(\Leftarrow\)) Suppose \(a, b \in \mathbb{Z}^+\) and suppose \(\operatorname{lcm}(a,b) = b\). \(\dots\) Therefore \(a \mid b\). \(\square\)
This direction was left blank on the slides — the completed argument (via \(g = \gcd(a,b)\), \(a = gm\), \(b = gn\) with \(\gcd(m,n) = 1\), so \(\operatorname{lcm}(a,b) = gmn\)) is written out in gcd-lcm-and-euclidean-algorithm.
Method 2: prove both directions simultaneously — be careful! Quicker, but easy to make a logical error, because every step must genuinely be reversible:
Suppose \(a, b \in \mathbb{Z}^+\) and suppose \(a \mid b\). This is true iff \(\exists k \in \mathbb{Z}\) such that \(b = ka\), which holds iff \(\operatorname{lcm}(a,b) = \operatorname{lcm}(a,ka)\), which holds iff \(a \mid ka\) and \(ka \mid ka\) and no smaller \(n > 0\) has \(ka \mid n\), which holds iff \(\operatorname{lcm}(a,ka) = ka\), which holds iff \(\operatorname{lcm}(a,b) = b\). \(\square\)
Each “iff” is doing real work here — if any one of them is only an implication, the proof silently collapses to a single direction.
Challenge activity — reversing the Euclidean algorithm
Non-assessed content.
Theorem: for \(a, b, c \in \mathbb{Z}\), if \(\gcd(a,b) \mid c\) then there exist integers \(x\) and \(y\) such that \(ax + by = c\).
Given \(ax + by = c\), use the Euclidean algorithm to find \(\gcd(a,b)\), then run the steps in reverse to find \(x\) and \(y\).
Example: find integers \(x, y\) satisfying \(1232x + 5859y = 14\).
Step 1 — use the E.A. to find \(\gcd(1232, 5859) = 7\):
\[5859 = 1232 \cdot 4 + 931 \quad \text{(Eqn 1)}\] \[1232 = 931 \cdot 1 + 301 \quad \text{(Eqn 2)}\] \[931 = 301 \cdot 3 + 28 \quad \text{(Eqn 3)}\] \[301 = 28 \cdot 10 + 21 \quad \text{(Eqn 4)}\] \[28 = 21 \cdot 1 + 7 \quad \text{(Eqn 5)}\] \[21 = 7 \cdot 3 + 0\]
Step 2 — work backwards to get \(1232w + 5859z = 7\):
From Eqn 5: \(7 = 28 - 21\). Use Eqn 4 to replace the 21 and collect like terms: \(7 = 28 - (301 - 28 \cdot 10) = 28 \cdot 11 - 301\). Use Eqn 3 to replace the 28: \(7 = (931 - 301 \cdot 3)\cdot 11 - 301 = 931 \cdot 11 - 301 \cdot 34\). Use Eqn 2 to replace the 301: \(7 = 931 \cdot 11 - (1232 - 931)\cdot 34 = 931 \cdot 45 - 1232 \cdot 34\). Use Eqn 1 to replace the 931: \(7 = (5859 - 1232 \cdot 4)\cdot 45 - 1232 \cdot 34 = 5859 \cdot 45 - 1232 \cdot 214\).
Step 3 — multiply through to get \(1232x + 5859y = 14\):
Therefore \(7 = 1232(-214) + 5859(45)\), so \(14 = 1232(-428) + 5859(90)\).
See also
- gcd-lcm-and-euclidean-algorithm · modular-arithmetic · divisibility-and-factorisation
- 2026-08-20-modular-arithmetic — Lecture 11
- practice-problems — §15 The Euclidean Algorithm, with full worked solutions