The Lumenary · Grades 9–12

Divisibility, Euclid's algorithm and unique factorisation

Name: ______________________

Date: ______________________

You will learn to

Use the definition of divisibility and division with remainder to prove basic facts about divisors
Compute $\gcd(a, b)$ with Euclid's algorithm, prove that the algorithm works, and express the gcd as $ax + by$ (Bézout's identity)
Prove Euclid's lemma — if a prime $p$ divides $ab$ , then $p$ divides $a$ or $p$ divides $b$ — and see why primality is needed
Prove the existence and uniqueness of prime factorisation, and explain why uniqueness needs a proof
Deduce that a fraction in lowest terms has a terminating decimal exactly when its denominator has no prime factors other than 2 and 5
Distinguish the greatest common divisor from the least common multiple, and compute both

1.
Use Euclid's algorithm to compute $\gcd(252, 198)$ .
2.
Which pairs $(x, y)$ satisfy $5x + 3y = 1$ ? (Choose all that apply.)
- A. $(2, -3)$
- B. $(-1, 2)$
- C. $(1, -1)$
- D. $(-4, 7)$
- E. $(3, -4)$
3.
For which of these numbers $d$ is it true that for all integers $a, b$ : if $d \mid ab$ then $d \mid a$ or $d \mid b$ ? (Choose all that apply.)
- A. $d = 2$
- B. $d = 4$
- C. $d = 6$
- D. $d = 7$
- E. $d = 9$
4.
Compute $\operatorname{lcm}(84, 90)$ .
5.
Which of these fractions have a terminating decimal expansion? (Choose all that apply.)
- A. $\tfrac{7}{40}$
- B. $\tfrac{1}{12}$
- C. $\tfrac{3}{12}$
- D. $\tfrac{11}{125}$
- E. $\tfrac{2}{15}$
6.
In the proof of Euclid's lemma we assume $p \mid ab$ and $p \nmid a$ , and then say $\gcd(p, a) = 1$ . Why?
- A.The positive divisors of $p$ are only $1$ and $p$ , and $p$ does not divide $a$ , so the only positive common divisor is $1$ .
- B.By Bézout's identity.
- C.Because $a < p$ .
- D.Any two different numbers are coprime.
7.
With a $6$ -litre jug, a $15$ -litre jug and a tap, what is the smallest positive amount of water you can measure exactly (by filling, emptying and pouring between the jugs)?
8.
In the Hilbert numbers $1, 5, 9, 13, 17, 21, \dots$ (numbers of the form $4k + 1$ ), which statement is true?
- A. $441 = 9 \cdot 49 = 21 \cdot 21$ are two different factorisations into irreducibles, so unique factorisation fails.
- B. $9$ is not irreducible, because $9 = 3 \cdot 3$ .
- C.Euclid's lemma still holds: if an irreducible divides a product, it divides a factor.
- D.Some Hilbert numbers have no factorisation into irreducibles at all.
9.
Which Lean statement correctly formalises Euclid's lemma for natural numbers?
- A.∀ p a b : ℕ, p.Prime → p ∣ a * b → p ∣ a ∨ p ∣ b
- B.∀ p a b : ℕ, p ∣ a * b → p ∣ a ∨ p ∣ b
- C.∀ p a b : ℕ, p.Prime → p ∣ a ∨ p ∣ b → p ∣ a * b
- D.∀ p a b : ℕ, p.Prime → p ∣ a * b → p ∣ a ∧ p ∣ b
10.
Write extended_gcd(a, b) for natural numbers a, b (not both zero), returning a triple (g, x, y) with g == gcd(a, b) and a * x + b * y == g. Use the recursion: if b == 0 return (a, 1, 0); otherwise get (g, x, y) for (b, a % b) and back-substitute using a % b == a - (a // b) * b.
Computational — Practice

Answer key — Divisibility, Euclid's algorithm and unique factorisation

1.
$252 = 1 \cdot 198 + 54$ , $\;198 = 3 \cdot 54 + 36$ , $\;54 = 1 \cdot 36 + 18$ , $\;36 = 2 \cdot 18 + 0$ . The last non-zero remainder is $18$ , so $\gcd(252, 198) = 18$ . (Check: $252 = 18 \cdot 14$ , $198 = 18 \cdot 11$ , and $14, 11$ are coprime.)
2.
$(2, -3)$ , $(-1, 2)$ and $(-4, 7)$ work. Bézout's coefficients are not unique: from one solution $(x, y)$ we get others $(x + 3t, y - 5t)$ for every integer $t$ , since $5 \cdot 3t - 3 \cdot 5t = 0$ .
3.
Exactly the primes, $2$ and $7$ . If $d = st$ is composite with $1 < s, t < d$ , then $d \mid s \cdot t$ although $d \nmid s$ and $d \nmid t$ (both are smaller than $d$ and positive). In fact this property characterises primes among integers greater than $1$ .
4.
$\operatorname{lcm}(84, 90) = 2^2 \cdot 3^2 \cdot 5 \cdot 7 = 1260$ . Check with the formula: $\gcd(84, 90) = 2 \cdot 3 = 6$ and $84 \cdot 90 / 6 = 7560 / 6 = 1260$ .
5.
In lowest terms the denominators are $40 = 2^3 \cdot 5$ , $12 = 2^2 \cdot 3$ , $4 = 2^2$ (for $\tfrac{3}{12} = \tfrac14$ ), $125 = 5^3$ and $15 = 3 \cdot 5$ . By Theorem 8, exactly $\tfrac{7}{40}$ , $\tfrac{3}{12}$ and $\tfrac{11}{125}$ terminate. The reduction step matters: Theorem 8 is about fractions in lowest terms.
6.
Any common divisor of $p$ and $a$ divides $p$ , so (taking it positive) it is $1$ or $p$ . It cannot be $p$ , since $p \nmid a$ . Hence $\gcd(p, a) = 1$ , and Bézout then gives $px + ay = 1$ . For a composite $d$ this step fails — which is why $4 \mid 2 \cdot 2$ does not force $4 \mid 2$ .
7.
Every amount obtained is a combination $6x + 15y$ , so it is a multiple of $\gcd(6, 15) = 3$ ; and $3 = 15 - 2 \cdot 6$ can be measured: fill the $15$ -litre jug, then pour from it into the $6$ -litre jug twice (emptying the small jug in between). So the answer is $3$ litres.
8.
$9$ , $21$ and $49$ are irreducible among Hilbert numbers (their only proper factorisations in $\Z$ use $3$ and $7$ , which are not of the form $4k + 1$ ), and $9 \cdot 49 = 21 \cdot 21 = 441$ . Existence of factorisations still holds, but uniqueness and Euclid's lemma fail — because there is no Bézout identity in this system.
9.
Euclid's lemma is ∀ p a b : ℕ, p.Prime → p ∣ a * b → p ∣ a ∨ p ∣ b. Dropping p.Prime makes it false (4 ∣ 2 * 2), replacing ∨ by ∧ makes it false (2 ∣ 2 * 3), and reversing the implication gives a different, easy statement.
10.
```
def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x, y = extended_gcd(b, a % b)
    return (g, y, x - (a // b) * y)
```
This is the same back-substitution as the Lean definition xgcd, whose correctness (bezout) is proved for all inputs. On $(1071, 462)$ it returns $(21, -3, 7)$ : $1071 \cdot (-3) + 462 \cdot 7 = 21$ .