Euclidean Algorithm Calculator

About the Euclidean Algorithm Calculator

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 page 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, the output keeps the division steps and the Bézout back-substitution in the same view.

When This Page Helps

Use this page when you need more than the final gcd. It keeps the quotient-remainder chain, Bézout coefficients, and derived LCM together so you can follow the algorithm from the first division through the final back-substitution.

How to Use the Inputs

1. Enter two positive integers in the input fields.
2. Click a preset button to load a classic GCD example.
3. Review the output cards for GCD, LCM, and Bézout coefficients.
4. Examine the steps table for the full division chain.
5. Check the back-substitution table for extended algorithm details.
6. Use the visual bars to see relative sizes of the inputs and GCD.

Example Calculation

Tips & Best Practices

• Check that all inputs use the same scale and assumptions before trusting the result.
• Compare the answer with the worked example or a rough estimate to catch entry mistakes.

How the Euclidean Algorithm Works

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.

The Extended Algorithm and Bézout's Identity

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.

Applications in Cryptography and Computer Science

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.

Frequently Asked Questions

• What is the Euclidean algorithm?

  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.

• What are Bézout coefficients?

  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.

• How do you get LCM from GCD?

  LCM(a, b) = |a × b| / GCD(a, b). This identity connects the two fundamental concepts.

• What does it mean if GCD is 1?

  The two numbers are coprime (relatively prime) — they share no common factor other than 1. This is important in modular arithmetic and cryptography.

• How is this used in cryptography?

  The extended Euclidean algorithm computes modular inverses, which are essential for RSA encryption, Diffie-Hellman key exchange, and other public-key cryptosystems.

• How efficient is the Euclidean algorithm?

  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.

• Can this handle negative numbers?

  The GCD is always positive. This calculator takes the absolute value of inputs. The Bézout coefficients may be negative.