Seeing the method in action
For 252 and 105: 252=2×105+42, 105=2×42+21, and 42=2×21+0. The last nonzero remainder is 21.
Math calculator
Euclidean Algorithm Calculator
Trace repeated quotient-and-remainder divisions that produce the greatest common divisor. Input changes update both gcf and divisions and the supporting steps.
Euclidean Algorithm inputs
Complete the fields
Reading the calculation
The Euclidean algorithm uses gcd(a,b)=gcd(b,a mod b). Each remainder is smaller than the preceding divisor, so the process must terminate. Euclidean Algorithm also connects with direct GCF.
A correct gcf and divisions is reliable for Euclidean Algorithm only when the chosen model fits the problem.
Calculating it by hand
Divide the larger magnitude by the smaller, replace the pair with divisor and remainder, and repeat until the remainder is zero.
Before accepting the Euclidean Algorithm result
The inputs cannot both be zero. Signs are removed because the conventional GCF is nonnegative.
Carry the available precision through euclidean algorithm, then round the final output rather than its intermediate parts.
Practical meaning
It efficiently finds GCFs for large integers and supplies the division chain used by the extended algorithm and modular inverses. A related application of Euclidean Algorithm is Bézout coefficients.
Checking the model and magnitude
For this euclidean algorithm calculation, the labels first integer and second integer carry mathematical meaning. A transposed entry can remain numerically valid while describing an entirely different setup.
Swapping the inputs changes at most the first displayed division but not the final GCF. A small controlled input change is enough to test the expected direction.
An exact expression can preserve factors, radicals, or π that a decimal hides. Use the representation suited to the next task and label it clearly as gcf and divisions.
A GCF calculator reports the endpoint; this page exposes the quotient-and-remainder path. Checking the requested noun is often enough to select the right model.
Reproducibility here depends on the inputs more than the interface. Preserve first integer and second integer, the operation shown, and enough unrounded digits for the next calculation.
Why each replacement is safe
Writing a=qb+r shows that every common divisor of a and b also divides r=a−qb. The reverse is also true, so replacing (a,b) with (b,r) preserves the complete common-divisor set. The shrinking remainder changes the numbers without changing the GCF sought.
Questions about Euclidean Algorithm
Why does the algorithm stop?
Each nonzero remainder is a smaller nonnegative integer.
What is the last nonzero remainder?
The GCF.
Do negative inputs matter?
Only their magnitudes matter for the GCF.