Pattern visualizer
GCD of Two Numbers
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. Animated on: Compute the greatest common divisor of a = 48 and b = 18 using the Euclidean algorithm. Answer: 6..
Math
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).
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