Compute GCD via the Euclidean algorithm with step-by-step division, extended Euclidean algorithm, Bézout coefficients, LCM, presets, steps table, and visual representation.
The **Euclidean Algorithm Calculator** computes the greatest common divisor (GCD) of two integers using the classical Euclidean algorithm, one of the oldest known algorithms in mathematics — dating back to Euclid's *Elements* around 300 BC. Enter any two positive integers and see the step-by-step division process, the quotient and remainder at each stage, and the final GCD.
Beyond the basic algorithm, this tool also performs the **extended Euclidean algorithm**, which finds integers x and y (Bézout coefficients) such that ax + by = gcd(a, b). These coefficients are essential for computing modular inverses, solving linear Diophantine equations, and many cryptographic algorithms including RSA key generation.
The calculator displays the LCM (least common multiple) derived from the GCD using the identity LCM(a, b) = |a × b| / GCD(a, b). You can also explore co-primality — whether the two numbers share no common factor other than 1. A detailed steps table shows every division with the dividend, divisor, quotient, and remainder. The back-substitution table then traces how the Bézout coefficients are built from these remainders.
Preset buttons load classic examples like GCD(252, 105) = 21 and larger cases for practice. A visual bar representation shows the relative sizes of the two numbers and their GCD. Whether you are learning number theory, studying for a math competition, or implementing cryptographic algorithms, this calculator provides the full picture.
The Euclidean algorithm itself is straightforward, but the extended version's back-substitution to find Bézout coefficients is multi-step and error-prone, especially for large numbers. This calculator performs both the standard and extended algorithms, displays every quotient-remainder step, and computes x and y such that ax + by = GCD(a, b). Cryptography students solving modular-inverse problems, programmers implementing RSA, and math students checking homework all benefit from the instant step-by-step trace.
GCD(a, b): Divide a by b to get remainder r. Replace a with b, b with r. Repeat until r = 0. The last non-zero remainder is the GCD. Extended: find x, y such that ax + by = GCD(a, b).
Result: 2×105 + 42
GCD(252, 105): 252 = 2×105 + 42, then 105 = 2×42 + 21, then 42 = 2×21 + 0. GCD = 21. Extended: 21 = 1×252 + (−2)×105, so x = 1, y = −2.
The algorithm is based on the identity GCD(a, b) = GCD(b, a mod b). Starting with two positive integers, you divide the larger by the smaller, note the remainder, and repeat with the divisor and remainder until the remainder is zero. The last non-zero remainder is the GCD. For 252 and 105: 252 = 2×105 + 42, then 105 = 2×42 + 21, then 42 = 2×21 + 0. The GCD is 21. The algorithm terminates in O(log min(a, b)) steps — remarkably efficient even for numbers with hundreds of digits.
Bézout's identity guarantees that for any integers a and b, there exist integers x and y such that ax + by = GCD(a, b). The extended Euclidean algorithm finds x and y by back-substituting through the division steps. From our example: 21 = 105 − 2×42 = 105 − 2×(252 − 2×105) = 3×105 − 2×252, attempting... actually 21 = 1×252 + (−2)×105. This result has profound applications: computing modular inverses (if GCD(a, m) = 1, then x from ax + my = 1 is a⁻¹ mod m), solving linear Diophantine equations, and establishing key relationships in number theory.
The extended Euclidean algorithm is at the heart of RSA encryption: to compute the private key d, you need the modular inverse of e modulo φ(n), which is exactly what the extended algorithm provides. Diffie-Hellman key exchange, elliptic-curve cryptography, and Chinese Remainder Theorem implementations all rely on modular inverses as well. Beyond cryptography, the algorithm appears in fraction simplification (divide numerator and denominator by their GCD), continued-fraction expansion, lattice reduction, and even music theory (computing rhythmic patterns based on GCD relationships). Its O(log n) efficiency makes it one of the earliest and most ubiquitous algorithms in computer science.
An ancient method for finding the greatest common divisor of two integers by repeatedly dividing the larger by the smaller and taking the remainder until the remainder is zero. Use this as a practical reminder before finalizing the result.
Integers x and y such that ax + by = GCD(a, b). They are found using the extended Euclidean algorithm by back-substituting through the division steps.
LCM(a, b) = |a × b| / GCD(a, b). This identity connects the two fundamental concepts.
The two numbers are coprime (relatively prime) — they share no common factor other than 1. This is important in modular arithmetic and cryptography.
The extended Euclidean algorithm computes modular inverses, which are essential for RSA encryption, Diffie-Hellman key exchange, and other public-key cryptosystems. Keep this note short and outcome-focused for reuse.
Very efficient — it runs in O(log(min(a, b))) steps, making it practical even for very large numbers. It is one of the fastest known GCD algorithms.
The GCD is always positive. This calculator takes the absolute value of inputs. The Bézout coefficients may be negative.