QuickCalculators runs Euclid's algorithm on two nonnegative integers, printing every quotient and remainder until the GCF appears as the last nonzero remainder. Enter the pair in either order; the step table shows the division form so each line can be checked by hand.
Find the GCF by repeated division
Euclid's algorithm finds the greatest common factor by dividing the larger number by the smaller and replacing the larger with the remainder, then repeating. When a remainder of zero appears, the divisor from that step is the GCF. Euclid's Algorithm Calculator records each division so the chain is auditable.
For 816 and 2260, begin with 2260 ÷ 816. The quotient is 2 and the remainder is 628. Next, 816 ÷ 628 leaves remainder 188. Continue until a zero remainder stops the chain. The final nonzero remainder is the GCF of the original pair.
Read the step table
The step table lists dividend, divisor, quotient, and remainder for every round. Reading down the remainder column shows the shrinking sequence that ends at zero. QuickCalculators aligns those columns so a notebook copy can verify a × b + r equals the prior dividend on each row.
A compact sketch for 48 and 18:
| Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
The last nonzero remainder is 6, so GCF(48, 18) = 6.
Avoid this common mistake
The subtraction form and the division form are the same algorithm. Division is repeated subtraction compressed into one quotient. Students sometimes treat them as rival methods with different answers. Both terminate at the same GCF when applied correctly. Subtracting 18 from 48 twice reaches 12, which is exactly what quotient 2 encodes in one line.
Preferring division saves writing without changing the mathematical path Euclid described.
Understand why the algorithm always terminates
Each remainder is a nonnegative integer strictly smaller than the previous divisor, so the remainder sequence cannot descend forever. Finite descent forces a zero remainder after finitely many steps. That guarantee holds for all nonnegative integer inputs the page accepts.
Worst-case pairs related to Fibonacci numbers need more steps than typical classroom examples, yet still finish. The step count grows roughly with the logarithm of the inputs for ordinary random pairs, which is why Euclid's method scales past listing factors.
Frequently asked questions
What is Euclid's algorithm?
Euclid's algorithm is a method for finding the greatest common factor of two nonnegative integers by repeated division with remainder. The last nonzero remainder is the GCF. The calculator prints each of those division steps.
How does Euclid's algorithm find the GCF?
Euclid's algorithm finds the GCF by replacing the larger number with the remainder after division by the smaller number, repeating until the remainder is zero. The divisor used in the final nonzero-remainder step is the GCF.
What is the GCF of 816 and 2260?
The GCF of 816 and 2260 is found by running Euclid's algorithm on that pair and reading the last nonzero remainder from the step table. Enter both integers on this page to see every quotient and remainder in order.
Why does Euclid's algorithm work?
Euclid's algorithm works because any common divisor of a and b is also a common divisor of b and a mod b. Replacing the pair with the smaller number and the remainder preserves the GCF until the remainder hits zero.
How many steps does Euclid's algorithm take?
The number of steps Euclid's algorithm takes depends on the inputs; each remainder is smaller than the prior divisor, so the process is finite. Fibonacci-like pairs need more steps than average, but typical classroom numbers finish quickly.
What is the difference between the subtraction and division forms?
The subtraction form repeatedly subtracts the smaller from the larger; the division form subtracts in bulk using a quotient. Both forms compute the same GCF. Division is just repeated subtraction written compactly.
Summary
Euclid's Algorithm Calculator finds a GCF by repeated division and shows every quotient and remainder in a step table. Pairs such as 48 and 18 end at remainder 6, matching GCF(48, 18). Subtraction and division forms are the same algorithm at different levels of compression. Remainders strictly decrease, so the process always terminates for nonnegative integers.