How the Euclidean Algorithm Works
The Euclidean algorithm finds the greatest common divisor (GCD) of two integers a and b — the largest positive integer that divides both without a remainder — through repeated division. At each step it replaces the larger number with the remainder of dividing it by the smaller: gcd(a, b) = gcd(b, a mod b), continuing until the remainder reaches 0. The divisor at that final step is the GCD. Described by Euclid around 300 BCE, it remains the standard, efficient method for computing GCDs by hand or by computer.
Step-by-step division
To find gcd(48, 18): divide 48 by 18 to get a quotient of 2 and a remainder of 12 (48 = 2×18 + 12). Replace the pair with (18, 12) and repeat: 18 = 1×12 + 6. Replace with (12, 6): 12 = 2×6 + 0. The remainder is now 0, so the algorithm stops — the last nonzero remainder, 6, is gcd(48, 18). This calculator runs exactly this sequence on your two integers and reports how many division steps it took.
LCM and Bézout coefficients
Once the GCD is known, the least common multiple follows directly from lcm(a, b) = |a × b| / gcd(a, b), because the product of two integers always equals the product of their GCD and LCM. The calculator also runs the extended Euclidean algorithm to find integers x and y satisfying Bézout's identity, a×x + b×y = gcd(a, b). These coefficients are not unique — infinitely many pairs satisfy the equation — but the extended algorithm returns one valid solution, which underlies modular inverse calculations used in cryptography (such as RSA key generation).
Common mistakes
- Using non-integers: the Euclidean algorithm is defined for integers — round or scale decimal values before entering them.
- Confusing GCD with LCM: the GCD is always less than or equal to the smaller input; the LCM is always greater than or equal to the larger input.
- Ignoring the sign convention: the GCD is conventionally reported as a non-negative number even when one or both inputs are negative.
Applications
- Simplifying a fraction to lowest terms by dividing the numerator and denominator by their GCD.
- Computing modular inverses in cryptography (for example, RSA key generation) using the extended Euclidean algorithm.
- Scheduling and synchronization problems, where the LCM finds when two repeating events next coincide.
- Computer science: the algorithm's efficiency — O(log(min(a, b))) division steps — makes it a building block in many number-theory routines.