This is an algorithm for efficiently finding the GCD of large numbers.
Principle of the Algorithm
GCD(a, b) = GCD(b, a mod b) (if the remainder when a is divided by b is r, then GCD(a,b)=GCD(b,r))
When r=0, b is the GCD
Example ① (Calculating with the Euclidean Algorithm)
Find GCD(323, 187).
323 = 187×1 + 136
187 = 136×1 + 51
136 = 51×2 + 34
51 = 34×1 + 17
34 = 17×2 + 0
Solution:GCD(323, 187) = 17
Find GCD(323, 187).
323 = 187×1 + 136
187 = 136×1 + 51
136 = 51×2 + 34
51 = 34×1 + 17
34 = 17×2 + 0
Solution:GCD(323, 187) = 17
Example ② (Determining Relatively Prime Numbers)
Find GCD(35, 24).
35 = 24×1 + 11
24 = 11×2 + 2
11 = 2×5 + 1
2 = 1×2 + 0
GCD = 1 → 35 and 24 are relatively prime
Find GCD(35, 24).
35 = 24×1 + 11
24 = 11×2 + 2
11 = 2×5 + 1
2 = 1×2 + 0
GCD = 1 → 35 and 24 are relatively prime
Key Points
- Euclidean algorithm: repeatedly calculate the remainder when the larger number is divided by the smaller number
- When the remainder becomes 0, the last divisor is the GCD
- GCD(a,b)=1 ⟺ a and b are relatively prime
Practice Problems
- Find GCD(273, 91) using the Euclidean algorithm.
- Find GCD(437, 209) using the Euclidean algorithm.
- Find all natural numbers n no greater than 20 satisfying GCD(n, 12)=4.
Solutions and Explanations
- 273=91×3+0 → GCD=91
- 437=209×2+19、209=19×11+0 → GCD=19
- n=4k (a multiple of 4) and GCD(n,12)=4 → k and 3 are relatively prime (k is not a multiple of 3). n≤20 → k=1,2,4,5 → n=4,8,16,20 (20=4×5、GCD(20,12)=4 ✓) → 4, 8, 16, 20