GCD of Two
The key insight: the greatest common divisor (GCD) of two numbers does not change if we replace the larger number with its remainder upon division by the smaller. Euclidean algorithm repeatedly replaces (a, b) with (b, a % b) — the last non-zero remainder is the GCD. This reduces the problem size rapidly because the remainder is always smaller than the divisor, guaranteeing termination. We show each (a, b) pair transition step by step.
Details
Animated on: Compute the greatest common divisor of a = 48 and b = 18 using the Euclidean algorithm. Answer: 6.
Problem:GCD of TwoEasy
Math
step 1 / 9
Initial values: a = 48, b = 18. We'll compute GCD(48, 18) using the Euclidean algorithm. The algorithm repeatedly replaces (a, b) with (b, a % b).
- a=0· arr[0] = 48
- b=1· arr[1] = 18
1FUNCTION gcd(a, b):2 WHILE b > 0:3 temp = remainder of a divided by b4 a = b5 b = temp6 RETURN a
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Initial values: a = 48, b = 18. We'll compute GCD(48, 18) using the Euclidean algorithm. The algorithm repeatedly replaces (a, b) with (b, a % b).
- temp = a % b = 48 % 18 = 12. Compute the remainder of a divided by b; 48 ÷ 18 = 2 remainder 12, so temp = 12.
- a = b = 18. Replace a with the old b; a is now 18. b = temp = 12. The pair is now (18, 12).
- temp = a % b = 18 % 12 = 6. Compute the new remainder; 18 ÷ 12 = 1 remainder 6, so temp = 6.
- a = b = 12. Replace a with the old b; a is now 12. b = temp = 6. The pair is now (12, 6).
- temp = a % b = 12 % 6 = 0. Compute the remainder; 12 ÷ 6 = 2 remainder 0, so temp = 0.
- a = b = 6. Replace a with the old b; a is now 6. b = temp = 0. The pair is now (6, 0).
- b = temp = 0. The loop exit condition b > 0 is no longer satisfied (b = 0). The algorithm terminates.
- Return a = 6. The last non-zero remainder is the GCD; GCD(48, 18) = 6.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.