Euclidean Algorithm Calculator
Discover the Greatest Common Divisor (GCD) of two numbers with this interactive tool.
Calculation Result
The Greatest Common Divisor (GCD) of and is:
Euclidean Algorithm Steps:
- Step : = × +
- Final Step: The GCD is the last non-zero remainder, which is .
About the Euclidean Algorithm
The Euclidean Algorithm is an efficient method for computing the Greatest Common Divisor (GCD) of two integers. The GCD is the largest positive integer that divides each of the integers. The algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. This process is repeated until one of the numbers becomes zero, at which point the GCD is the other number.
For example, to find the GCD of 48 and 18:
- Divide 48 by 18 to get a quotient of 2 and a remainder of 12 (48 = 18 × 2 + 12).
- Now divide 18 by the remainder 12 to get a quotient of 1 and a remainder of 6 (18 = 12 × 1 + 6).
- Next, divide 12 by the remainder 6 to get a quotient of 2 and a remainder of 0 (12 = 6 × 2 + 0).
- Since the remainder is now 0, the GCD is the last non-zero remainder, which is 6.
Source: Wikipedia