Remainders down to the gcd

Mathematics · Number Theory · ages 18-19

Name ______________________ Date ____________

What is the greatest common divisor of 48 and 18?
- 6
- 12
- 9
- 3
What is the first division step when running Euclid's algorithm on 270 and 192?
- 270 = 192 times 2 plus 78
- 270 = 192 times 1 plus 78
- 270 = 78 times 3 plus 36
The remainders in Euclid's algorithm keep shrinking, so the algorithm always stops.
Circle one: True False
Running Euclid's algorithm on 1071 and 462 gives remainders 147, 21, 0. What is the gcd? Type the number.
Answer: ______________
What is the greatest common divisor of 99 and 78?
Answer: ______________
Why must Euclid's algorithm terminate?
- Remainders grow, so new factors appear
- Division is exact at every step
- Remainders shrink, and shrinking whole numbers must reach 0
Running Euclid's algorithm on 108 and 30 starts with 108 divided by 30. What is the first remainder? Type the number.
Answer: ______________
The first step of the Euclidean algorithm on 1071 and 462 divides 1071 by 462 and keeps the remainder. What is that remainder?
- 147
- 117
- 165
- 141
Pat runs Euclid on 1071 and 462, sees remainders 147, 21, 0, and reports the gcd as 147. What is wrong?
- He should have listed all divisors instead; Euclid fails on large pairs
- He took the first remainder instead of the last nonzero one; the gcd is 21
- He divided in the wrong order; the gcd is 147 times 21
Euclid's lemma says: if a prime p divides a product a x b, then what follows?
- p divides a or p divides b
- p divides a and also divides b
- p equals a times b
- p divides neither a nor b

Answer key

For grown-ups. Fold this page away before handing over the rest.

6 · 48 = 2 x 2 x 2 x 2 x 3 and 18 = 2 x 3 x 3, so the shared prime factors give 2 x 3 = 6.
270 = 192 times 1 plus 78 · 192 fits once into 270 with 78 left over.
True · Shrinking whole numbers must reach 0, so the run always ends.
21 · The remainders run 147, 21, 0, so the last nonzero one is 21.
3 · 99 = 9 x 11 = 3 x 3 x 11 and 78 = 6 x 13 = 2 x 3 x 13, so they share a single factor 3.
Remainders shrink, and shrinking whole numbers must reach 0 · Each remainder is smaller than the last, forcing the run to end.
18 · 108 = 30 times 3 plus 18, so the first remainder is 18.
147 · 462 x 2 = 924, and 1071 - 924 = 147, so the first remainder is 147.
He took the first remainder instead of the last nonzero one; the gcd is 21 · The gcd is the remainder just before zero, which is 21.
p divides a or p divides b · That is exactly Euclid's lemma: a prime divisor of a product must divide at least one factor. From it follows that prime factorisation is unique.