Euclidean Algorithm
Repeatedly replace (a,b) by (b, a mod b) until the remainder is 0.
Key idea
Repeatedly replace (a,b) by (b, a mod b) until the remainder is 0.
In depth
Based on gcd(a, b) = gcd(b, a mod b): replace the pair by the smaller number and the remainder until the remainder is 0. The last non-zero remainder is the GCD. It is fast and needs no factorization.
Worked example
gcd(252, 105): 252 = 2×105 + 42; 105 = 2×42 + 21; 42 = 2×21 + 0. GCD = 21.
Formula
Real-world uses
- Fast computing in software, such as simplifying fractions in calculators and checking coprime numbers in codes
Common mistake
Stopping one step early or returning 0 instead of the last non-zero remainder.
How to learn this
- Read the key idea and say it in your own words.
- Work through the worked example, then try a similar problem.
- Use the interactive lesson’s visual and mini-quiz to check the pattern.
Frequently asked questions
What is Euclidean Algorithm?
Repeatedly replace (a,b) by (b, a mod b) until the remainder is 0. It is a topic at the intermediate level in Arithmetic & Number Sense.
What is the formula for Euclidean Algorithm?
The key formula is gcd(a,b) = gcd(b, a mod b).
Where is Euclidean Algorithm used in real life?
Real-world examples: Fast computing in software, such as simplifying fractions in calculators and checking coprime numbers in codes.
What should I learn before Euclidean Algorithm?
Make sure you are comfortable with Least Common Multiple, the previous topic in Arithmetic & Number Sense.
What is a common mistake with Euclidean Algorithm?
Stopping one step early or returning 0 instead of the last non-zero remainder.
How can I practise Euclidean Algorithm?
Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.
What comes after Euclidean Algorithm?
Move on to Exponents (Powers) next.
Related intermediate topics in Arithmetic & Number Sense
- Long Multiplication – Multiply by each digit of the multiplier, shift by place value, then add partial products.
- Long Division – Divide, multiply, subtract and bring down repeatedly to get the quotient.
- Factors and Multiples – Factors divide a number exactly; multiples are its products with whole numbers.
- Divisibility Rules – Quick tests: by 2 last digit even, by 3 digit-sum divisible by 3, by 5 ends 0/5, by 9 digit-sum divisible by 9.
- Prime Numbers – A prime has exactly two positive divisors: 1 and itself.
- Composite Numbers – Numbers greater than 1 with more than two factors.