Euclidean Algorithm Calculator

a = q * b + r, so gcd(a, b) = gcd(b, r); repeat until r = 0, and then b is the answer

a = q * b + r

One round of the algorithm, written as an equation. a is the larger of the two numbers on this round, b the smaller, q is how many whole times b fits into a, and r is what is left over. This is the page's steps notation exactly: 1071 = 2 * 462 + 147 is one round

a, b

The two numbers being compared. They change identity every round — the b of one round becomes the a of the next, and the r becomes the new b. That shuffle is why the input fields are not named dividend and divisor: on round one 1071 is the dividend, on round two it is 462, and a label that is right for one round is wrong for the others

q

The quotient, how many whole times b goes into a. It is always at least 1, because the pair is put in descending order before the loop starts — which is also why you will never see q = 0 here. The only round where q is unremarkable is the last one, where the remainder is zero and the quotient is exact

r

The remainder, always smaller than b and never negative. The algorithm's stopping rule is r = 0, printed as the last round rather than omitted: 147 = 7 * 21 + 0 is the line that says the search is over and 21 is the answer

gcd(a, b)

The greatest common factor: the largest whole number dividing both a and b evenly. The answer is the b of the final round, taken straight out of the loop rather than recomputed. For 1071 and 462 it is 21, which is why 1071 = 21 × 51 and 462 = 21 × 22, and no larger number divides both

610 = 1 * 377 + 233

The opening round of the worst case: consecutive Fibonacci numbers. Every quotient here is 1 and the numbers barely shrink, which is what makes this pair take thirteen rounds. Lamé's theorem says no pair of numbers this size can take more

Reducing a fraction is the everyday use. To write 462/1071 in lowest terms you need the greatest common factor of the two, and this page hands you that plus the evidence — 21, and the three rounds that produced it. Dividing top and bottom by 21 gives 22/51, and the printed steps are what let you check the reduction rather than trust it. The same need appears whenever a ratio has to be simplified: gear ratios, screen aspect ratios, scale drawings, and any two measurements you want to express as a proportion rather than as a pair of numbers. The second use is in code and in classwork, where the algorithm is taught as the first interesting one: it terminates, it is fast, and it is correct for a reason you can see in a single equation. It is also the standard way to compute a modular inverse — the extended version carries two extra numbers along the same rounds — which is the step inside RSA key generation. A third use is a sanity check on factoring. Finding that 1071 is 3 × 357 and 462 is 2 × 3 × 7 × 11 is work; finding that their greatest common factor is 21 is three divisions, so running this page first tells you whether simplifying is going to be easy before you start. When all you want is the answer and not the process, gcf-calculator asks the same question in a shorter form and handles more than two numbers at once; lcm-calculator uses the factor to get the least common multiple, since lcm = (a / gcd) * b; remainder-calculator covers what a single remainder means when the numbers can be negative, which this page never has to deal with.

1. The textbook pair: 1071 and 462

   1. How many times does 462 fit into 1071? Twice, and 2 × 462 = 924, leaving 1071 − 924 = 147
   2. Now the pair is 462 and 147: 147 fits into 462 three times, 3 × 147 = 441, leaving 21
   3. Now the pair is 147 and 21: 21 fits into 147 exactly seven times, leaving 0
   4. The remainder is zero, so the algorithm stops and the answer is 21

   The default input, and the worked example this algorithm is usually introduced with. Two checks are worth running on the result. Divide both numbers by 21 and you get 51 and 22, which share no factor, and that is what makes 21 the greatest rather than merely a common factor. And note that nothing here involved factoring: to find the factors of 1071 by trial division you would work up to 32, whereas the algorithm only ever divided a number by one it already had in hand. Three rounds, each one cheaper than the last.

2. One round is enough: 12 and 60

   1. Put the pair in descending order: 60 first, 12 second
   2. 60 = 5 × 12 + 0, so 12 divides 60 exactly
   3. The remainder is zero immediately, so the algorithm stops after one round
   4. The answer is 12 — the smaller of the two, because it divides the larger

   The shortest possible non-trivial run, and the case that shows why the final round is printed rather than skipped. The line 60 = 5 * 12 + 0 is the whole answer: it says the remainder reached zero, which is the only way this algorithm ever stops. Drop that line and the steps would be empty, and a reader would have no way to tell a one-round answer from a page that had not run. Whenever one number divides the other exactly, the greatest common factor is simply the smaller one.

3. Coprime numbers: 9 and 20

   1. 20 = 2 × 9 + 2, so the pair becomes 9 and 2
   2. 9 = 4 × 2 + 1, so the pair becomes 2 and 1
   3. 2 = 2 × 1 + 0, so the algorithm stops
   4. The answer is 1, which means 9 and 20 share no factor above 1

   A greatest common factor of 1 is a real answer, not a failure, and it has a name: the numbers are coprime. It is also the sign that the fraction 9/20 is already in lowest terms, so no simplification is available. Notice that the rounds did not collapse — the algorithm walked all the way down to 1 through three steps, because neither number ever divided the other exactly. Coprime pairs are the common case as numbers grow: the chance that two numbers picked at random share a factor falls away quickly, which is exactly what makes the method useful for building a modular inverse in cryptography.

Both numbers must be whole, and both must lie between 1 and 1000000. Zero is refused rather than treated as a special case. The greatest common factor of a and 0 is a, which is a perfectly good answer, but this page cannot show it: the first round would be a = q * 0 + r, and that q does not exist. Rather than print a process with a hole in it, the page declines the input. Negative numbers are refused for the same reason — the steps as printed assume both numbers are at least 1, and a negative operand would need a rule for what the quotient and remainder mean that this page does not state anywhere. The ceiling of 1000000 is not about the algorithm, which would happily run on far larger numbers; it is there so every subtraction, multiplication and remainder on the way is exact in ordinary double-precision arithmetic, and so the printed steps cannot run to a length that stops being readable. Two fairly small numbers can still produce many rounds — 610 and 377 take thirteen — but the count is capped in practice by the ceiling, and the reference table has a rounds column so you can see it vary. The steps are printed as equations — a = q * b + r, joined by semicolons — and not as long division, so if you are looking for the familiar division bracket this page will not give it to you. The inputs are interchangeable: the page sorts them into descending order before starting, so you cannot use this page to see what 3 = 0 * 5 + 3 would look like, because that round is never produced. If your numbers can be negative, or if you want the remainder convention spelled out, remainder-calculator is the page for that question.

What is the greatest common factor, in one sentence?

The largest whole number that divides both numbers exactly, leaving no remainder. For 1071 and 462 it is 21: 1071 = 21 × 51 and 462 = 21 × 22, and 51 and 22 share no factor, which is what makes 21 the greatest. Note that 3 and 7 also divide both numbers — they are common factors, just not the greatest one. The page's primary output is always this number, and the steps below it are the evidence.

Why does the last step always end in + 0?

Because a remainder of zero is the only thing that stops the algorithm. The loop replaces the pair with a smaller pair — the second number, and the remainder — and the numbers fall every round, so they must eventually reach zero. 147 = 7 * 21 + 0 is the round where that happens, and the greatest common factor is the divisor of that round, 21. The page prints it rather than hiding it because a steps list that stopped at the last non-zero remainder would leave the reader to work out that the search was over.

Does the order I type the two numbers in matter?

No. The page puts them in descending order before the first round, so 462 and 1071 produce exactly the same three lines as 1071 and 462. That is a choice rather than a property of the algorithm — the rule gcd(a, b) = gcd(b, a) means either order gives the right answer — but without the sort the first line would read 3 = 0 * 5 + 3 for the pair 3 and 5, which is a legal division but reads as though dividing a small number by a larger one were part of the method. It is also why the input fields are called first number and second number rather than dividend and divisor: those two roles swap on every round.

What does an answer of 1 mean?

That the two numbers share no factor above 1, which is a complete answer rather than a failure. Such numbers are called coprime, and the pair 9 and 20 on this page is one example. It also tells you something practical: the fraction 9/20 is already in lowest terms, so no simplification is available. As numbers get larger, coprime pairs become the common case, which is why the method matters in cryptography — building an RSA key means finding numbers that share no factor with a given one.

Will bigger numbers always take more rounds?

No, and the reference table is there to make that concrete. 1000000 and 999998 finish in two rounds, while 610 and 377 — three digits each — take thirteen. What forces many rounds is not size but how slowly the numbers shrink, and the slowest-shrinking pairs are consecutive Fibonacci numbers, where every remainder is close to the divisor. That result is Lamé's theorem, and it puts a ceiling on the round count that grows only with the number of digits, which is why the algorithm is considered fast.

How is this different from just factoring both numbers?

Factoring is much more work, and it is work this page never does. To factor 1071 by trial division you would test divisors up to its square root, about 32; the algorithm instead divides a number by one it already holds, and it finishes in three rounds. For small numbers like these the difference is invisible, but factoring gets dramatically harder as numbers grow while the Euclidean algorithm barely notices. That gap is the entire reason it is still taught, and it is also why the answer above comes out of the loop rather than from a second computation — running both would risk the printed steps disagreeing with the number printed above them.

• Euclidean Algorithm — the recurrence gcd(a, b) = gcd(b, a mod b), the proof that it terminates, and the connection to continued fractions — Wolfram MathWorld (United States)
• Greatest Common Divisor — what the greatest common factor is, and why gcd(a, 0) = a is the base case the algorithm stops on — Wolfram MathWorld (United States)
• Lamé's Theorem — the result that the pair taking the most rounds for its size is always a pair of consecutive Fibonacci numbers — Wolfram MathWorld (United States)
• 教育部关于印发义务教育课程方案和课程标准（2022 年版）的通知——The fifth item in the annex list of this notice is the Mathematics Curriculum Standards for Compulsory Education (2022 edition); the greatest common divisor is part of the Number and Algebra strand in the upper primary grades, and the wording of the standards and the grade-band breakdown are governed by that annex — 中华人民共和国教育部