Use this if you want the gcd of two polynomials.
Iterative, at each step K is the iteration counter, Q is the quotient, and R is the remainder. S and T give you the multiplication factors.
Let’s say we want gcd of f(x) and g(x), with deg(f) ≥ deg(g):
| K | Q | R | S(x) | T(x) |
|---|---|---|---|---|
| 0 | - | f(x) | 1 | 0 |
| 1 | f(x) / g(x) | g(x) | 0 | 1 |
| 2 | g(x) / R₂ | rem( f(x)/g(x) ) | q₁ s₁ + s₀ | q₁ t₁ + t₀ |
| 3 | R₂ / R₃ | rem( g(x)/R₂ ) | q₂ s₂ + s₁ | q₂ t₂ + t₁ |
| 4 | R₃ / R₄ | rem( R₂/R₃ ) | q₃ s₃ + s₂ | q₃ t₃ + t₂ |
| 0 | ⇒ R₄ is the gcd |
This solves the equation r(x) = t(x) f(x) + s(x) g(x) as R₄ = t₄ f + s₄ g.