Euclidean algorithm calculator
For 1071 and 462 the greatest common divisor is 21, reached in three divisions: 1071 = 462 × 2 + 147, then 462 = 147 × 3 + 21, then a remainder of zero. Enter two integers and see every step, not just the answer. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- A
- 1,071
- B
- 462
- Gcd
- 21
- Steps count
- 3
The Euclidean algorithm calculator takes two integers and computes their greatest common divisor the way Euclid described it over two thousand years ago: by repeatedly dividing and keeping the remainder. Instead of returning only the final number, it returns the full step list — every line of the form dividend = divisor × quotient + remainder — so you can see exactly how the answer was reached. It accepts negative values (the GCD uses absolute values), rejects non-integer input, and refuses the undefined case gcd(0,0).
What the Euclidean algorithm actually does
The greatest common divisor of two integers is the largest number that divides both without leaving a remainder. The Euclidean algorithm finds it without factoring anything, which is why it stays fast even for very large inputs. The idea is simple: if a number divides both a and b, it also divides the remainder of a divided by b.
So you replace the pair (a, b) with (b, a mod b) and repeat. Each step is one long division — for example, 1071 = 462 × 2 + 147 — and you keep going until the remainder is zero. The last non-zero remainder is the GCD.
Because the remainder strictly shrinks at every step, the loop is guaranteed to end, and it ends quickly: the number of steps is proportional to the logarithm of the smaller input.
Inputs, edge cases and how errors are reported
You send two fields, a and b, and both must be integers. Negative integers are fine: the GCD is defined on absolute values, so gcd(-1071, 462) is the same as gcd(1071, 462), and the step list is computed on the absolute values. Zero is a valid input for one of the fields — gcd(a, 0) is |a|, and in that case the step list is empty because no division is needed — but both fields being zero is rejected, because gcd(0,0) is mathematically undefined.
Where a step-by-step GCD earns its place
The bare GCD is a commodity — every language has one in its standard library. What this capability adds is the trace. Teachers and students use the step list to verify that an exercise was solved with the actual Euclidean algorithm rather than by guessing divisors.
Developers use it when debugging fraction simplification, aspect-ratio reduction or coprimality checks, because seeing 252 = 105 × 2 + 42 pinpoints where a hand computation diverged from the code. Cryptography learners meet the algorithm as the foundation of the extended version that produces Bézout coefficients and modular inverses; watching the plain division steps first makes that leap much easier.
What you can do with it
Check a worked exercise
Paste the two numbers from a homework problem and compare your written division steps against the ones the algorithm actually produces.
Simplify fractions and ratios
Get the GCD of a numerator and denominator to reduce a fraction, with the step list as an audit trail for how the divisor was found.
Teach the algorithm before the extended version
Show students the plain division trace first, then move to Bézout coefficients and modular inverses built on the same loop.
FAQ
Why does it reject gcd(0,0)?
Because the greatest common divisor of zero and zero is undefined — every integer divides zero, so there is no greatest one. Provide at least one non-zero value.
Can I pass negative numbers?
Yes. The GCD is computed on absolute values, so gcd(-1071, 462) returns the same result as gcd(1071, 462).
What does the steps array contain?
One object per division: dividend, divisor, quotient and remainder, so each line reads dividend = divisor × quotient + remainder. The last non-zero remainder is the GCD.
How large can the inputs be?
Up to the maximum safe integer, 9007199254740991, so every quotient and remainder in the output is exact.
How does the Euclidean algorithm find the GCD?
It divides the larger number by the smaller one and keeps the remainder, then repeats with the smaller number and that remainder. For 1071 and 462 the remainders are 147, then 21, then 0, so the greatest common divisor is 21.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/math/euclidean-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/euclidean-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/euclidean-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"a": 1071,
"b": 462
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.euclidean_algorithm",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_abs | 9007199254740991 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
The same code runs free in your browser on this page and through the paid API.
What the Euclidean algorithm actually does
This endpoint performs exactly that procedure and hands you back every division it made, not just the conclusion, which makes it useful both for checking homework and for auditing a computation inside a larger system.
Inputs, edge cases and how errors are reported
Numeric strings that represent exact integers, such as "1071", are accepted; decimals, fractions, scientific notation and non-numeric values are rejected with an invalid_input error that explains what was wrong. Values are bounded by the safe integer range of IEEE 754 doubles, about 9 quadrillion, so every quotient and remainder in the output is exact. Errors never produce a partial answer: the request is refused with a machine-readable code and a message you can show to a user.
Technical questions
What does it cost?
$0.002 per request via the API. It is also free to run in your browser on this page.
What counts as an integer?
A JSON number with no fractional part, or a string of digits with an optional leading sign. Decimals, scientific notation and non-numeric values are rejected with an invalid_input error.