Euclidean algorithm: GCD by successive divisions

The principle

$\gcd(a, b)$ doesn’t change if we replace $a$ by the remainder of $a$ divided by $b$.

$\gcd(a, b) = \gcd(b, r) \quad \text{where } a = bq + r$

Repeat until the remainder is 0. The last nonzero remainder is the GCD.

Step-by-step

Example: $\gcd(252, 105)$.

Step	Division	Quotient	Remainder
1	252 = 105 × 2 + 42	2	42
2	105 = 42 × 2 + 21	2	21
3	42 = 21 × 2 + 0	2	0

$\gcd(252, 105) = 21$.

Another example

$\gcd(1071, 462)$:

• 1071 = 462 × 2 + 147
• 462 = 147 × 3 + 21
• 147 = 21 × 7 + 0

GCD = 21.

Why it works

Each step strictly reduces the numbers. The algorithm terminates. GCD is preserved at each step (Euclid’s lemma).

Applications

• Simplify a fraction: divide top and bottom by their GCD.
• Solve Diophantine equation $ax + by = c$: solvable iff $\gcd(a, b) \mid c$.
• Cryptography: extended Euclid appears in RSA.

Common mistakes

1. Stopping too early: continue until remainder is 0.
2. Wrong remainder: GCD is the LAST NONZERO remainder.
3. Confusing remainder and quotient.

?À toi de jouer

GCD(48, 18) by Euclidean algorithm?

A.6B.2C.12D.3

Valider