Extended Euclidean Algorithm Calculator finds integer coefficients whose linear combination equals the GCD of the original inputs, provided at least one input is nonzero.
Check the coefficients against the original integers
The extended Euclidean algorithm returns the GCD and integer coefficients x and y such that a × x + b × y equals that GCD. Enter the original signed integers in their labeled order. The coefficient x multiplies input a, and y multiplies input b. The ordinary Euclidean algorithm tracks remainders. Its extended form also tracks each remainder’s coefficients in the original inputs. Each new remainder is the old remainder minus the quotient times the current remainder; its coefficients follow the same subtraction. Calculation details show both the division equations and the coefficient rows, including the original-input check. Barrus and Clark’s textbook chapter explains this construction.
Keep the original signs and omit thousands separators, decimal points and scientific notation.
Review the named primary result and open calculation details to check the arithmetic.
Extended Euclid for 803 and 154: worked example
The textbook preset enters a = 803 and b = 154. The engine returns GCD 11, x = 5 and y = -26. Its checked identity is:
803 × (5) + 154 × (-26) = 11
803 = 5 × 154 + 33
154 = 4 × 33 + 22
33 = 1 × 22 + 11
22 = 2 × 11 + 0
The boxed example in Barrus and Clark’s chapter gives the same original-input coefficients.
Read the quotient, remainder and coefficient rows
The quotient is the whole-number part of the division of the current nonnegative magnitudes. The remainder is the amount left after subtracting that multiple. Coefficient rows represent those same remainders as linear combinations of the original signed inputs; they are not coefficients of a reordered unlabeled pair.
The initial rows describe each magnitude using its original input and sign. Every subsequent row is checked against the original-input identity. Stop when the remainder becomes zero; the preceding nonzero remainder and its coefficients supply the final GCD identity. The final zero row is a check, not the GCD row. The ordinary GCF page supplies the divisor-only result when coefficients are unnecessary.
For the GCD of three or more integers, the Greatest Common Factor Calculator folds the pair result through the list. This tool returns coefficients for exactly two original inputs; it does not compute a coefficient for each member of a longer list.
Nonunique coefficients, signs and modular inverses
Bézout coefficients are not unique. This implementation preserves input order, performs Euclid on nonnegative magnitudes and restores the original signs in the coefficients. A different valid pair can still satisfy the same identity. The signed preset checks -240 × (9) + 46 × (47) = 2.
When input b is a positive modulus greater than one and the GCD is one, reducing x modulo that input gives its normalized modular inverse. This follows by reducing a × x + b × y = one modulo b. The inverse preset has a = 3, b = 11 and x = 4; its inverse residue is 4. If the GCD is larger than one, no such inverse exists. A zero or negative input b is accepted for the identity but is not used as an inverse modulus.
At least one integer must be nonzero. Each input may contain up to 64 digits, with exact integer-string arithmetic and no rounding of coefficients. Decimal points, exponents and unsafe numeric API values are rejected. This page does not solve polynomial identities or generate cryptographic keys.
Factors Calculator lists every positive divisor and signed factor pair of one nonzero integer; Prime Factorization Calculator decomposes one integer into prime powers and repeated factors; Greatest Common Factor Calculator finds the greatest divisor shared by an integer list; Least Common Multiple Calculator finds the smallest positive shared multiple of nonzero integers, with an explicit zero convention.