BTT Mathematics / Primary Mathematics Learning Hub / Euclidean Algorithm
The greatest common divisor (GCD) of two positive whole numbers is the largest positive whole number that divides both exactly. Listing factors works for small numbers. Euclid’s algorithm provides a more efficient route by replacing a pair of numbers with a smaller pair that has the same GCD.
If a=bq+r, then any common divisor of a and b also divides the remainder r=a−bq. Conversely, any common divisor of b and r divides a=bq+r. Therefore gcd(a,b)=gcd(b,r).
For 48 and 18:
48=2×18+12
18=1×12+6
12=2×6+0
The last non-zero remainder is 6, so gcd(48,18)=6.
This guide is Primary Mathematics enrichment. It deepens Factors, Multiples and Divisibility, Remainder Cycles and Fractions of a Quantity, Equivalence and Operations.
The named algorithm is optional enrichment. Use the MOE Primary curriculum page and the learner’s school programme for required content.
Meaning of GCD · Repeated remainders · Why it works · Reduce fractions · GCD and LCM · Coprime numbers · 24 questions · Worked answers
1. GCD is a shared exact grouping
The common divisors of 18 and 48 are 1,2,3 and6. The greatest is six. This means 18 and48 can both be partitioned into groups of size six with no remainder, and no larger positive group size works for both.
Worked example A: 84 and 30
Common factors can be listed, but Euclid is shorter:
84=2×30+24
30=1×24+6
24=4×6
So gcd(84,30)=6.
Worked example B: One number divides the other
1001=7×143. The remainder is zero on the first division, so gcd(1001,143)=143.
Worked example C: Coprime pair
For 987 and610, the Euclidean process eventually reaches remainder one. Therefore gcd=1. Numbers with GCD one are called coprime or relatively prime.
2. Replace the larger number by the remainder
At each stage, divide the larger number by the smaller and keep the remainder. Then use the old smaller number and the new remainder as the next pair. Stop when the remainder becomes zero.
Worked example D: 252 and 105
252=2×105+42
105=2×42+21
42=2×21+0
Thus gcd=21.
Worked example E: 391 and 299
391=1×299+92
299=3×92+23
92=4×23
So gcd=23.
Worked example F: 202 and 78
202=2×78+46
78=1×46+32
46=1×32+14
32=2×14+4
14=3×4+2
4=2×2
The last non-zero remainder is 2.
3. The remainder keeps exactly the same common divisors
Suppose a=qb+r. If d divides both a and b, then d divides a−qb=r. So every common divisor of a and b is a common divisor of b and r.
Conversely, if d divides both b and r, then it divides qb+r=a. So every common divisor of b and r is a common divisor of a and b.
The two pairs therefore have the same set of common divisors and the same greatest one. Repeating the replacement does not change the GCD; it only makes the numbers smaller.
Worked example G: 1071 and 462
1071=2×462+147
462=3×147+21
147=7×21
Each pair—(1071,462), (462,147), (147,21)—has GCD 21.
Why subtraction also works
Replacing a larger number a by a−b preserves the GCD for the same reason. Euclid’s division step performs many repeated subtractions at once, which is more efficient.
4. GCD gives the largest one-step fraction reduction
To reduce a fraction a/b, divide numerator and denominator by their GCD. This keeps the fraction equivalent because both parts are scaled by the same non-zero factor.
Worked example H: 84/126
gcd(84,126)=42. Divide both by42: 84/126=2/3.
Worked example I: 150/210
gcd=30, so 150/210=5/7.
Worked example J: 391/299
gcd=23. Since 391=17×23 and299=13×23, 391/299=17/13.
Worked example K: 420/96
gcd(420,96)=12. Therefore 420/96=35/8. A reduced fraction need not be proper.
Worked example L: 1071/462
gcd=21, so 1071/462=51/22.
5. GCD and LCM are linked for positive whole numbers
For positive a and b,
gcd(a,b) × lcm(a,b) = a×b.
This can find the least common multiple after the GCD is known.
Worked example M: 48 and 18
gcd=6. Therefore lcm=(48×18)÷6=144.
Worked example N: 84 and 30
gcd=6. lcm=(84×30)÷6=420.
Why the product identity is plausible
The GCD captures the shared prime-factor contribution while the LCM captures the largest required contribution of each prime. Their product reconstructs the two original prime-factor collections together. Full prime-factor proof is optional extension.
6. GCD one means no non-trivial common factor
If gcd(a,b)=1, the pair is coprime. The numbers themselves need not be prime. For example, 8 and15 are both composite relationships to other numbers, but they share no factor larger than one.
Worked example O: Consecutive numbers
Any two consecutive positive integers are coprime. Any common divisor of n and n+1 must also divide their difference one, so the GCD is one.
Worked example P: Reduced fractions
A fraction is in lowest terms exactly when its numerator and denominator are coprime. If gcd is greater than one, further reduction is possible.
Worked example Q: Remainder zero stopping rule
The algorithm stops when the next remainder is zero. The divisor at that step is the last non-zero remainder and therefore the GCD.
7. Practice: 24 original questions
Questions 1–8: Compute GCDs
1. Find gcd(48,18).
2. Find gcd(84,30).
3. Find gcd(252,105).
4. Find gcd(144,96).
5. Find gcd(391,299).
6. Find gcd(202,78).
7. Find gcd(1001,143).
8. Find gcd(987,610).
Questions 9–16: Reduce fractions using the GCD
9. Reduce 84/126.
10. Reduce 150/210.
11. Reduce 96/144.
12. Reduce 252/378.
13. Reduce 391/299.
14. Reduce 202/78.
15. Reduce 420/96.
16. Reduce 1071/462.
Questions 17–24: Remainders, LCM and reasoning
17. Use Euclid’s algorithm to find gcd(1071,462).
18. How many division-with-remainder steps are used in the chain 1071,462 before the remainder becomes zero?
19. Find gcd(210,45).
20. Find lcm(48,18) using gcd×lcm=product.
21. Find lcm(84,30) using the same identity.
22. What does gcd(a,b)=1 tell you about a and b?
23. If a=qb+r, explain why any common divisor of a and b must divide r.
24. If the first division of a by b gives remainder zero, with a≥b>0, what is gcd(a,b)?
8. Worked answers
Answers 1–8
1. 6. 48=2×18+12; 18=12+6; 12=2×6.
2. 6.
3. 21.
4. 48. 144=1×96+48; 96=2×48.
5. 23.
6. 2.
7. 143. 1001=7×143.
8. 1. The pair is coprime.
Answers 9–16
9. 2/3. Divide by42.
10. 5/7. Divide by30.
11. 2/3. Divide by48.
12. 2/3. gcd(252,378)=126.
13. 17/13. Divide by23.
14. 101/39. Divide by2.
15. 35/8. Divide by12.
16. 51/22. Divide by21.
Answers 17–24
17. 21. 1071=2×462+147; 462=3×147+21; 147=7×21.
18. 3 divisions. The third produces remainder zero.
19. 15. 210=4×45+30; 45=1×30+15; 30=2×15.
20. 144. (48×18)÷6.
21. 420. (84×30)÷6.
22. They are coprime. Their only positive common divisor is one.
23. If d divides a and b, then d divides a−qb=r because multiples and differences of divisible quantities remain divisible by d.
24. b. Remainder zero means b divides a exactly, so the smaller number b is the GCD.
9. Teaching and transfer
If a learner loses track of the algorithm, write each division in the form larger=quotient×smaller+remainder. Then circle the old smaller number and the new remainder: those become the next pair.
When the quotient is mistaken for the GCD
The quotient controls how many copies are removed; the remainder carries the unresolved common-divisor information. The final answer is the last non-zero remainder, not the last quotient.
When factor listing is faster
For tiny numbers such as 12 and18, listing factors may be simpler. Euclid becomes more valuable as the numbers grow or factorization is not obvious. Algorithm choice is part of mathematical efficiency.
When fraction reduction is done in several small steps
That method is valid, but the GCD gives the largest possible one-step reduction. Both routes should end with numerator and denominator coprime.
When remainder zero is overlooked
Stop immediately. If the smaller number divides the larger exactly, it is already the GCD.
Connect to algorithms
Euclid’s method is a clean example of a finite loop with a decreasing state: remainders get smaller until zero appears. This connects directly to Mathematical Algorithms, Flowcharts and Decision Trees.
Continue through this enrichment collection
For lattice-area relationships, use Pick’s Theorem, Lattice Points and Coordinate Area. For reflection geometry, use Paper Folding, Crease Patterns and Symmetry. For fraction order and mediants, use Farey Sequences, Mediants and Fraction Neighbours.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. Euclid’s algorithm is presented for positive whole-number GCDs; fraction reduction uses positive denominators.