Greatest Common Divisor (GCD) Calculator
Calculation Steps (Euclidean Algorithm)
Enter two integers to see the steps.
Understanding GCD
The Greatest Common Divisor (GCD) of two or more integers (where at least one is not zero) is the largest positive integer that divides each of the integers without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
The concept of the GCD is ancient, appearing in Euclid's Elements (around 300 BC). Euclid described an efficient method for computing the GCD, now known as the Euclidean algorithm. It's one of the oldest algorithms still in common use and relies 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 (or, more efficiently, its remainder when divided by the smaller number).
The GCD has numerous applications in mathematics and computer science. It's fundamental in number theory, used in simplifying fractions to their lowest terms (by dividing both numerator and denominator by their GCD), solving Diophantine equations, and is a key component of algorithms like the RSA encryption system.