Extended Euclidean Coefficients
Find exact decimal coefficients x and y satisfying a·x+b·y=gcd(a,b), with a nonnegative gcd and deterministic coefficients even when both inputs are zero.
Description
Bézout’s identity represents the gcd of two integers as their integer linear combination.
Bézout’s identity represents the gcd of two integers as their integer linear combination. Extended Euclid computes both the gcd and coefficients.1
The tool returns gcd, x, y. The indexing and output conventions below determine how to read these values.
When to use Extended Euclidean Coefficients
Use this for the following task: Find exact decimal coefficients x and y satisfying a·x+b·y=gcd(a,b), with a nonnegative gcd and deterministic coefficients even when both inputs are zero. Use the input and output conventions below to reproduce the intended mathematical quantity.
How to use Extended Euclidean Coefficients and understand its results
- Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
- Enter a, b according to the field table, then run the tool.
- Read gcd, x, y. Preserve exact decimal strings and the stated indexing or coefficient order.
- Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.
| Input field | Meaning | Value type and bounds | Requirement |
|---|---|---|---|
| a | First signed integer | string (integer/arbitrary); maximum text length 200; pattern ^-?(0|[1-9][0-9]*)$ | Required |
| b | Second signed integer | string (integer/arbitrary); maximum text length 200; pattern ^-?(0|[1-9][0-9]*)$ | Required |
Read signed decimal strings with BigInt, run Euclid on absolute values while updating two coefficient pairs, then restore signs to the coefficients.
a×x+b×y=gcd(a,b), with gcd≥0 The symbols and boundary conditions refer to the supplied fields and the implementation described above.
| Output field | Meaning | Value type |
|---|---|---|
| gcd | Greatest common divisor | string (integer/arbitrary) |
| x | Coefficient of a | string (integer/arbitrary) |
| y | Coefficient of b | string (integer/arbitrary) |
{
"input": {
"a": "240",
"b": "46"
},
"output": {
"gcd": "2",
"x": "-9",
"y": "47"
}
}Limitations and assumptions
Coefficients need not be unique; the tool returns its deterministic pair. Both inputs zero return gcd=0, x=1, y=0, and each input string is capped at 200 characters.
Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.
Alternative or Complementary methods
Choose Greatest Common Divisor of a List when you need its operation: Compute the nonnegative greatest common divisor of 1–1,000 signed decimal integers; an all-zero list has gcd zero. Choose Modular Inverse for the complementary operation: Find the least nonnegative inverse of a signed decimal integer modulo a decimal modulus of at least two, rejecting noncoprime pairs.
Background reference: The Euclidean Algorithm.
References
-
The Euclidean Algorithm — Wissam Raji, Mathematics LibreTexts
Similar or alternative tools
- Greatest Common Divisor of a List
Compute the nonnegative greatest common divisor of 1–1,000 signed decimal integers; an all-zero list has gcd zero.
- Modular Inverse
Find the least nonnegative inverse of a signed decimal integer modulo a decimal modulus of at least two, rejecting noncoprime pairs.