A numerical case for Euclidean Algorithm
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
What the displayed Euclidean Algorithm means
A correct gcf and divisions is reliable for Euclidean Algorithm only when the chosen model fits the problem.
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.
Reconstructing Euclidean Algorithm without the tool
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.
Common interpretation traps for Euclidean Algorithm
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.
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.
A practical audit of Euclidean Algorithm
Keep First integer integral when Euclidean Algorithm requires integers. Verify Second integer through the defining Euclidean Algorithm identity.
Test zero in Euclidean Algorithm, then test one in Euclidean Algorithm. Rebuild the starting integer through Euclidean Algorithm.
For a Euclidean Algorithm audit, retain First integer and Second integer. Decide the likely direction of GCF and divisions before rerunning Euclidean Algorithm. Change only Second integer; the response in GCF and divisions can then be traced within the Euclidean Algorithm setup.
Validating Euclidean Algorithm
Keep the units of First integer beside the Euclidean Algorithm work. Interpret Second integer under the same convention. The label attached to GCF and divisions should describe the quantity that the Euclidean Algorithm question actually requests.
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.