Euclidean Algorithm Calculator - GCD with Step-by-Step Chain

A Euclidean algorithm calculator is a tool that finds the greatest common divisor of two positive integers using the remainder-based method first described by Euclid around 300 BCE. Enter any two positive integers and the calculator returns the GCD along with a complete step-by-step record of the division and remainder chain used to reach it.

• • School and homework: Students working through number theory, modular arithmetic, or proof classes can verify their manual GCD work by comparing each division step.
• • Cryptography prep: RSA and Diffie-Hellman key generation depend on GCDs and modular inverses, both of which build on the Euclidean algorithm.
• • Reducing fractions: Fractions are reduced by dividing the numerator and denominator by their GCD, so the Euclidean algorithm is the engine behind any fraction simplifier.
• • Engineering, music, and craft: Problems that need evenly spaced repetitions, gear ratios, music intervals, or a least common multiple often reduce to a GCD calculation, since dividing a measurement by its GCD yields the smallest unit that tiles the original.

The Euclidean algorithm does not require factoring either number. It only needs the integer division and remainder at each step, so it stays fast even for inputs that are too large to factor by hand. Because each step strictly reduces the larger value, the algorithm always reaches a remainder of zero in at most five times the number of digits of the smaller input.

A Euclidean algorithm calculator therefore suits a wide range of users. Students use it to check homework. Engineers use it to simplify ratios and to size mechanical parts. Software developers use it to compute modular inverses, which appear in public-key cryptography and in computer algebra libraries.

When the goal is to reduce a fraction to lowest terms, the Simplify Fractions Calculator uses the same GCD value that this calculator returns as the divisor for both numerator and denominator.

The Euclidean algorithm is a recursive reduction that replaces the pair (a, b) with (b, a mod b) until the second value becomes zero. The last non-zero value is the greatest common divisor of the original pair.

• a: First positive integer, the dividend in the first step.
• b: Second positive integer, the divisor in the first step.
• q: Integer quotient floor(a / b) at each step.
• r: Remainder after the division, used as the next dividend.

Order does not matter. The algorithm naturally handles a < b because the first division step returns a quotient of zero and a remainder of a, then continues as if the pair had been swapped.

Every step strictly reduces the larger value, so the algorithm always terminates. The number of steps is bounded by five times the number of digits of the smaller input, which is why the Euclidean algorithm is considered the fastest general-purpose GCD method for positive integers.

According to Wolfram MathWorld (Euclidean Algorithm), the Euclidean algorithm is a recursive procedure that replaces the larger of two integers by their remainder until the remainder is zero, with the GCD equal to the last non-zero remainder.

Euclid's formula for right triangles relies on the same name, and Pythagorean Triples Calculator generates primitive triples using the related Euclid identity.

These four concepts explain why the algorithm works and how it connects to the rest of number theory.

Each row of the algorithm's step table is a remainder computation, which is the same operation that Modulo Calculator performs for any chosen modulus.

Follow these five steps to find the GCD and read the full step-by-step remainder chain that the calculator renders right under the results panel.

1. 1 Enter the first integer: Type the first positive integer in the box labeled Integer a. The default is 48 to match the canonical Euclid example.
2. 2 Enter the second integer: Type the second positive integer in the box labeled Integer b. The default is 18 so the first run reproduces the textbook result.
3. 3 Read the GCD result: Look at the right-hand panel. The top value is the greatest common divisor, displayed without units because it is a pure count.
4. 4 Walk the remainder chain table: Open the Remainder Chain table directly below the results. Each row shows the equation a = bq + r for one iteration, and the last row is highlighted with the GCD. The step count grows with the digit length of the smaller input, not the larger.
5. 5 Verify with the Bezout combination: The Bezout line in the results panel shows integers x and y such that ax + by equals the GCD. Plug the displayed x and y into that identity to confirm the result, or use the values to compute a modular inverse for cryptography work.

Try gcd(270, 192) by hand using the standard subtraction method and then compare with the calculator. The four-step chain in the worked examples shows exactly which remainder replaces which pair at each iteration, and the same chain will appear in the remainder chain table so you can mark up each row against your scratch work.

Once the GCD is known, dividing a fraction by another fraction usually requires the GCD of the new cross-products, and Divide Fractions Calculator walks through the same kind of integer reduction.

Automating the Euclidean algorithm gives students, engineers, and developers a fast, verifiable way to compute the GCD and inspect its derivation row by row.

• • Visible remainder chain: Every division, quotient, and remainder appears as a row in the chain table, so you can match each row against your own work and pin down exactly which step went wrong.
• • No factoring required: The algorithm uses only division and remainder, so it works for inputs that are far too large to factor by hand or by trial.
• • Cryptography-ready outputs: Bezout coefficients are returned automatically, which is exactly what you need to compute a modular inverse for RSA, Diffie-Hellman, or any extended algorithm downstream.
• • Time savings on multi-step work: A 30-step manual chain takes minutes to write out by hand. The calculator finishes the same chain in milliseconds and renders it in a table you can copy straight into a homework solution.
• • Error reduction for repeated use: Each row is computed by the same code path, so the risk of dropping a digit or skipping a step disappears once the calculator is part of the routine.
• • Connects to related number theory: The GCD output feeds directly into the simplify-fractions, lcm, and modular-inverse workflows that follow the Euclidean algorithm in any number-theory course.

Reducing both fractions with a shared GCD before comparing them is faster than cross-multiplication, which is the approach that Comparing Fractions Calculator uses under the hood.

These factors influence how many steps the algorithm takes and how the calculator presents the result.

• • This calculator accepts two positive integers. Three or more numbers require applying the algorithm iteratively, with the GCD of the third input computed against the running GCD of the first two.
• • The remainder chain table is capped at twelve visible rows so the page stays scannable. When the chain would run longer, the calculator collapses the extra rows into a single summary line that still reports the final step and the GCD.

According to Khan Academy (The Euclidean Algorithm), the Euclidean algorithm finds the greatest common divisor of two positive integers by repeatedly replacing the pair (a, b) with (b, a mod b) until b becomes zero.

When the GCD comes back as 1, the two inputs are coprime, which is the case to check before assuming a number is prime; the Prime Number Checker verifies single candidates and lists small prime factors so a GCD = 1 result is easy to interpret.