Euclidean Algorithm Calculator
Calculate the Greatest Common Divisor (GCD) using the Euclidean algorithm and find Bezout coefficients.
Enter Numbers
Division Steps
48 = 2 * 18 + 12
18 = 1 * 12 + 6
12 = 2 * 6 + 0
Algorithm
gcd(a, b) = gcd(b, a mod b)
gcd(a, 0) = a
Greatest Common Divisor
GCD(48, 18) = 6
GCD
6
LCM
144
Bezout Identity
Find x, y such that: a*x + b*y = gcd(a,b)
48 * (-1) + 18 * (3) = 6
x
-1
y
3
Properties
- gcd(a, b) = gcd(b, a)
- gcd(a, 0) = a
- gcd(a, 1) = 1
- a and b are coprime if gcd(a,b) = 1
- LCM(a, b) * GCD(a, b) = a * b