Extended GCD Polynomial Calculator

Compute exact rational polynomial Bézout witnesses u*f+v*g=monic gcd for degree≤12 integer input; coefficient strings preserve fractions and zero/zero returns all zeros.

Description

Polynomial Bézout coefficients exhibit a GCD as a linear combination of the inputs.

Polynomial Bézout coefficients exhibit a GCD as a linear combination of the inputs. Monic normalization requires scaling the witnesses as well as the GCD.^[1]

Compute exact rational polynomial Bézout witnesses u*f+v*g=monic gcd for degree≤12 integer input; coefficient strings preserve fractions and zero/zero returns all zeros.

When to use Extended GCD Polynomial Calculator

Use this tool to compute exact rational polynomial Bézout witnesses u*f+v*g=monic gcd for degree≤12 integer input; coefficient strings preserve fractions and zero/zero returns all zeros.

Choose the integer, sequence, coefficients or function parameters for your calculation. Follow the stated ordering, domain and size limits.

How to use Extended GCD Polynomial Calculator and understand its results

Choose the integer, sequence, coefficients or function parameters for your calculation. Follow the stated ordering, domain and size limits.
Enter leftPolynomial, rightPolynomial using the field table and calculation rules, then run the tool.
Read monicGcdCoefficients, leftBezoutCoefficients, rightBezoutCoefficients. The explanation below defines the units, signs, ordering and any flags or placeholder values.
If the tool reports an input issue, correct the values and run it again. Apply the stated assumptions when interpreting a successfully returned result.

Input field	Meaning	Value type; see rules below	Requirement
leftPolynomial	Left polynomial	list of number	Required
rightPolynomial	Right polynomial	list of number	Required

Supply nonempty constant-first signed integer coefficient lists of length ≤13 and magnitudes ≤one million. Use exact rational extended Euclidean division and return reduced fraction-string coefficient lists for the GCD and both witnesses. Two zero inputs return all three as ["0"].

left witness × left polynomial + right witness × right polynomial = monic GCD

Units, indexing, boundary conditions and exceptional cases are defined in the calculation rules above.

Output field	Meaning	Value type
monicGcdCoefficients	Monic gcd coefficients	list of string
leftBezoutCoefficients	Left bezout coefficients	list of string
rightBezoutCoefficients	Right bezout coefficients	list of string

json

{
  "input": {
    "leftPolynomial": [
      -1,
      0,
      1
    ],
    "rightPolynomial": [
      -1,
      1
    ]
  },
  "output": {
    "monicGcdCoefficients": [
      "-1",
      "1"
    ],
    "leftBezoutCoefficients": [
      "0"
    ],
    "rightBezoutCoefficients": [
      "1"
    ]
  }
}

Limitations and assumptions

Intermediate rational components have a 4096-digit budget. The witnesses need not be unique, although the computation fixes one result.

Numeric inputs and returned numeric values must be finite; an unrepresentable returned value produces an error. Numeric lists are limited to 100,000 entries; the rules above may require smaller limits. Missing required fields, extra fields, wrong value types and violations of the calculation rules are input errors.

Alternative or Complementary methods

Use Polynomial GCD Calculator: Exact polynomial GCD over rational coefficients from bounded integer input, normalized monic; zero result is ["0"], rational coefficients are exact decimal numerator/denominator strings. For a complementary task, use Polynomial LCM Calculator: Exact polynomial LCM over rational coefficients from bounded integer input, normalized monic; zero result is ["0"], rational coefficients are exact decimal numerator/denominator strings.

References

Extended GCD Polynomial Calculator — tool.io

Similar or alternative tools

Polynomial GCD Calculator
Exact polynomial GCD over rational coefficients from bounded integer input, normalized monic; zero result is ["0"], rational coefficients are exact decimal numerator/denominator strings.
Polynomial LCM Calculator
Exact polynomial LCM over rational coefficients from bounded integer input, normalized monic; zero result is ["0"], rational coefficients are exact decimal numerator/denominator strings.