Extended Euclidean calculator
For 240 and 46 the greatest common divisor is 2, and 240 × (−9) + 46 × 47 = 2. Enter two integers to get their divisor, the two Bézout coefficients and the equation that proves it. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- First integer
- 240
- Second integer
- 46
- Gcd
- 2
- X
- -9
- Y
- 47
- Check
- 2
The extended Euclidean algorithm does more than report the greatest common divisor of two integers: it also produces Bézout coefficients x and y such that a times x plus b times y equals that gcd. Those coefficients appear in modular inverses when the gcd is one, in constructive proofs of linear Diophantine equations, and in cryptography homework that needs an explicit combination rather than a bare remainder.
From remainders to Bézout coefficients
Ordinary Euclidean division repeatedly replaces a pair (a, b) with (b, a mod b) until the remainder is zero; the last non-zero remainder is gcd(a, b). The extended form keeps track of how each remainder is written as an integer linear combination of the original inputs. At every step the current remainder equals a times some coefficient plus b times another, and when the algorithm stops those coefficients are exactly the Bézout numbers for the gcd.
Classroom presentations often use back-substitution from the sequence of quotients; production code usually runs an iterative update of two coefficient pairs so no stack of remainders is stored. Both approaches compute the same mathematical object: integers x and y satisfying a*x + b*y = gcd(a, b). The gcd itself is always returned as a non-negative integer, matching the standard convention used in programming libraries and contest statements.
What you send and what you get back
The pair zero and zero is also rejected, because gcd(0, 0) is undefined and no coefficients can make a meaningful equation. On success the response includes the normalized a and b, gcd, x, y, a nested bezout object with the same coefficients, a numeric check equal to a*x + b*y, and an equation string such as 240*(-9) + 46*(47) = 2.
Typical checks: for 240 and 46 the gcd is 2 and one valid solution is x equals negative nine with y equals forty-seven; for a prime pair with gcd one the coefficients give a modular inverse of a modulo b after reducing x. Edge cases with a zero and a non-zero partner yield gcd equal to the absolute value of the non-zero input and a trivial coefficient pattern.
Where Bézout coefficients show up in real work
Contest programmers solve ax + by = c by first computing gcd and the base coefficients, then scaling and parametrizing the general solution when the gcd divides c. Cryptography students recover modular inverses for RSA toy examples and affine ciphers whenever gcd(a, m) equals one by reading the coefficient of a after reduction modulo m. Teachers assign constructive proofs that two integers are coprime and need a deterministic oracle that shows the combination, not only a true-or-false coprimality bit.
Data and systems engineers occasionally need explicit linear combinations when reconciling periodic schedules or stride arithmetic. Use the browser tool to check homework quickly, then automate the identical contract when your service needs bulk Diophantine checks. If you only need the plain gcd without coefficients, this landing still answers that need while teaching the stronger constructive result.
What you can do with it
Linear Diophantine equations
Obtain a particular solution (x, y) for a*x + b*y = gcd, then scale and parametrize when solving a*x + b*y = c in contests or homework.
Modular inverse building block
When gcd(a, m) = 1, reduce the Bézout coefficient of a modulo m to recover a modular inverse for crypto and number-theory exercises.
FAQ
What is the extended Euclidean algorithm?
It computes gcd(a, b) and integers x, y (Bézout coefficients) such that a*x + b*y equals that gcd, by tracking linear combinations through the Euclidean remainder steps.
Are the coefficients unique?
No. If (x, y) works, so does (x + k*(b/g), y - k*(a/g)) for any integer k. This tool returns one particular solution from the iterative algorithm.
What integer range is supported?
Each of a and b must be an integer with absolute value at most 9007199254740991 (Number.MAX_SAFE_INTEGER).
What does it cost?
The browser tool is free and runs locally.
How do I find the Bézout coefficients of 240 and 46?
Enter both numbers. The greatest common divisor is 2, and the coefficients are −9 and 47, because 240 × (−9) + 46 × 47 = 2. The result includes this equation so you can check it.
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/numth/extended-euclidean \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":240,"b":46}'const res = await fetch("https://api.kit.forhosting.com/numth/extended-euclidean", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 240,
"b": 46
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/extended-euclidean",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 240,
"b": 46
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/extended-euclidean", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":240,"b":46}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":240,"b":46}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/extended-euclidean", 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": 240,
"b": 46
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.extended_euclidean",
"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
From remainders to Bézout coefficients
This endpoint implements the iterative path on absolute values, then multiplies signs back so negative inputs still satisfy the identity.
What you send and what you get back
Provide integers a and b (aliases first or m for a, and second or n for b are accepted). Non-integers, empty fields, and values outside the platform safe-integer absolute maximum are rejected with invalid_input and are not charged.
Where Bézout coefficients show up in real work
Because the capability is a pure parse engine, there is no model drift, no network dependency, and no stored state: the same pair always yields the same JSON for a fixed coefficient convention. API pricing is the published base of $0.002 per successful item; failed validation does not consume balance.
Integration use cases
Teaching and automated checks
Show students the identity a*x + b*y = gcd with a stable JSON equation field, and wire the same contract into graders or CI fixtures.
Technical questions
Why are both a and b zero rejected?
gcd(0, 0) is undefined. There is no positive greatest common divisor, so the API returns invalid_input and does not charge.