Euclidean Algorithm Calculator
Compute gcd(a, b) by repeating a = bq + r until the remainder is 0. The page lists each division step so you can check homework against the classic Euclidean algorithm. Defaults are a = 1071 and b = 462.
Rated 4.7 out of 5 based on 241 reviews
How to run the Euclidean algorithm
- Enter two integers a and b. Absolute values are used, so signs do not change the gcd.
- Keep at least one of a or b non-zero. The pair 0, 0 is rejected.
- Read the GCD row first, then walk the Steps row to see each a = bq + r line.
- Compare the step count with your written work when a textbook asks you to show remainders.
- Open the plain GCD page when you only need the final divisor and not the intermediate remainders.
Euclidean algorithm
GCD by successive remainders for two integers
| Input a | First integer (absolute value used) |
|---|---|
| Input b | Second integer (absolute value used) |
| Division step | Write a = bq + r with 0 less than or equal to r less than |b| |
| Replacement | Replace (a, b) with (b, r) and repeat |
| Termination | Stop when r = 0; the current b (then stored as the leftover non-zero) is the gcd |
| Output | GCD value plus the list of remainder equations |
What the Euclidean algorithm shows
This spoke is the teaching view of gcd for exactly two integers. For 1071 and 462 the algorithm reaches gcd 21 and prints each remainder equation along the way.
Dividend, divisor, quotient, and remainder
Each step names a dividend and divisor, computes quotient q by truncating division, and remainder r = dividend mod divisor. The next step promotes the old divisor to the new dividend and the remainder to the new divisor.
How this page walks the remainders
The engine takes absolute values, then loops while the current divisor is non-zero. It appends strings of the form x = y × q + r, then shifts x to y and y to r. When the loop ends, the leftover non-zero value is the gcd.
When remainder steps matter
Proof courses and grade-school drills ask for the chain of equations, not only the answer. Use this page to verify that chain before you submit written work.
Limits
Exactly two integers. Lists of three or more values belong on the GCD page. Both inputs zero is invalid. Results are for checking arithmetic, not for certification. See the disclaimer.