Introduction

Around 300 BCE, Euclid described a way to find the greatest common divisor of two whole numbers without factoring either one: divide the larger by the smaller, keep the remainder, and repeat with the smaller number and that remainder. Do it enough times and the remainder hits zero — the last nonzero number was the GCD all along.

Nothing in that recipe actually requires numbers. It only needs two things: a way to divide with remainder, and a guarantee that the remainders keep getting smaller so the process must stop. Polynomials have both. You can divide one polynomial by another and get a quotient plus a remainder of strictly lower degree, just like long division with numbers.

Run Euclid's old trick on polynomials instead of integers and it still works — and what it hands you is the largest polynomial that divides both, which turns out to be exactly the piece built from their shared roots.

Try It

Below are two polynomials, A(x)A(x) and B(x)B(x), that happen to share a root. Press Step to run one round of polynomial division — divide the larger-degree polynomial by the smaller, keep the remainder — and watch the pair shrink. Press Run to the end to fast-forward straight to the answer.

<p class="hint">A(x) and B(x) below share a hidden root. Press <b>Step</b> to run one round of polynomial long division — divide A by B, keep the remainder — and watch the pair shrink toward their GCD.</p>
<div class="pair" id="pair"></div>
<div class="status" id="status">Press Step to begin dividing.</div>
<div class="log" id="log"></div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run to the end</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.pair { display: flex; flex-direction: column; gap: .4rem; margin: .4rem 0; }
.poly { font: 600 15px ui-monospace, monospace; background: #e8eef3; color: #1d3557;
        border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .7rem; }
.poly .label { font: 700 12px system-ui, sans-serif; color: #5a7088; margin-right: .4rem; }
.poly.zero { background: #f4f6f8; color: #9aa5b1; border-color: #e2e6ea; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.log { font: 500 13px ui-monospace, monospace; color: #444; background: #fafbfc;
       border: 1px solid #e2e6ea; border-radius: 8px; padding: .5rem .7rem;
       max-height: 130px; overflow-y: auto; white-space: pre-wrap; margin-bottom: .6rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Polynomials are stored as coefficient arrays, index = power of x, e.g. [6,1,-4,1] = 6 + x - 4x^2 + x^3.
// Starting pair: A = x^3 - 4x^2 + x + 6 = (x-2)(x+1)(x-3), B = x^2 + 2x - 8 = (x-2)(x+4). They share the root x = 2.
const START_A = [6, 1, -4, 1];  // A(x) = x^3 - 4x^2 + x + 6
const START_B = [-8, 2, 1];     // B(x) = x^2 + 2x - 8

// Drop trailing near-zero coefficients so the degree reflects the true polynomial.
function trim(p) {
  p = p.slice();
  while (p.length > 1 && Math.abs(p[p.length - 1]) < 1e-9) p.pop();
  return p;
}
function degree(p) {
  p = trim(p);
  return (p.length === 1 && Math.abs(p[0]) < 1e-9) ? -1 : p.length - 1;
}
function isZero(p) { return degree(p) === -1; }

// Polynomial long division: returns quotient q and remainder r such that a = q*b + r, deg(r) < deg(b).
function polyDivMod(a, b) {
  a = trim(a); b = trim(b);
  const db = degree(b);
  let rem = a.slice();
  const q = new Array(Math.max(degree(rem) - db + 1, 0)).fill(0);
  while (degree(rem) >= db) {
    const dr = degree(rem);
    const coef = rem[dr] / b[db];
    const shift = dr - db;
    q[shift] = coef;
    for (let i = 0; i < b.length; i++) rem[i + shift] -= coef * b[i];
    rem = trim(rem);
  }
  return { q: trim(q), r: trim(rem) };
}

// Render a coefficient array as a human-readable polynomial string, highest power first.
function fmtPoly(p) {
  p = trim(p);
  if (isZero(p)) return '0';
  const terms = [];
  for (let i = p.length - 1; i >= 0; i--) {
    const c = p[i];
    if (Math.abs(c) < 1e-9) continue;
    const av = Math.abs(c);
    const rounded = Math.abs(av - Math.round(av)) < 1e-6 ? Math.round(av) : Math.round(av * 1000) / 1000;
    let t;
    if (i === 0) t = String(rounded);
    else if (i === 1) t = (rounded === 1 ? '' : rounded) + 'x';
    else t = (rounded === 1 ? '' : rounded) + 'x^' + i;
    terms.push({ t, neg: c < 0 });
  }
  let s = '';
  terms.forEach((term, idx) => {
    if (idx === 0) s += (term.neg ? '-' : '') + term.t;
    else s += (term.neg ? ' - ' : ' + ') + term.t;
  });
  return s;
}

let A = START_A.slice();
let B = START_B.slice();
let finished = false;
let stepCount = 0;

function render() {
  const pair = document.getElementById('pair');
  pair.innerHTML = '';
  const rowA = document.createElement('div');
  rowA.className = 'poly' + (isZero(A) ? ' zero' : '');
  rowA.innerHTML = '<span class="label">A(x) =</span>' + fmtPoly(A);
  const rowB = document.createElement('div');
  rowB.className = 'poly' + (isZero(B) ? ' zero' : '');
  rowB.innerHTML = '<span class="label">B(x) =</span>' + fmtPoly(B);
  pair.appendChild(rowA);
  pair.appendChild(rowB);
  document.getElementById('step').disabled = finished;
  document.getElementById('run').disabled = finished;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

function appendLog(line) {
  const log = document.getElementById('log');
  log.textContent += (log.textContent ? '\n' : '') + line;
  log.scrollTop = log.scrollHeight;
}

// One Euclidean step: replace (A, B) with (B, remainder of A divided by B).
function step() {
  if (finished) return;
  if (isZero(B)) { finish(); return; }
  const { q, r } = polyDivMod(A, B);
  stepCount++;
  appendLog(fmt('Step %n%: %a% = (%q%) · (%b%) + (%r%)', {
    n: stepCount, a: fmtPoly(A), b: fmtPoly(B), q: fmtPoly(q), r: fmtPoly(r)
  }));
  A = B;
  B = r;
  if (isZero(B)) { finish(); return; }
  render();
  setStatus(fmt('Step %n% done — remainder is not zero yet. Keep going.', { n: stepCount }), '');
}

// Once B becomes the zero polynomial, A holds the GCD (up to a constant multiple).
function finish() {
  finished = true;
  render();
  // Normalize the result to be monic (leading coefficient 1) for a clean, canonical answer.
  const g = trim(A);
  const lead = g[degree(g)];
  const monic = g.map((c) => c / lead);
  setStatus(fmt('Done after %n% step(s) — GCD(A, B) = %gcd%.', { gcd: fmtPoly(monic), n: stepCount }), 'ok');
}

function runToEnd() {
  let guard = 0;
  while (!finished && guard < 100) { step(); guard++; }
}

function reset() {
  A = START_A.slice();
  B = START_B.slice();
  finished = false;
  stepCount = 0;
  document.getElementById('log').textContent = '';
  render();
  setStatus('Press Step to begin dividing.', '');
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('run').addEventListener('click', runToEnd);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console

Each step trades the pair (A,B)(A, B) for (B,R)(B, R), where RR is the remainder of dividing AA by BB. The degree of RR is always strictly smaller than the degree of BB, so after at most as many steps as the smaller polynomial's degree, the remainder must reach 00. Whatever is left — the last nonzero remainder — is the GCD.

The Real Complexity

The algorithm itself is fast: with polynomials of degree at most nn, each division reduces the degree by at least one, so the process terminates in at most nn steps, and each step costs O(n)O(n) arithmetic operations — an easy polynomial-time (in the size of the input) computation overall, much like Euclid's algorithm on integers.

But there is a catch that shows up the moment you leave the blackboard for a real computer:

  • Coefficient explosion. Every division step multiplies and subtracts coefficients, and if you keep everything as exact fractions, the numerators and denominators can grow exponentially in size after just a handful of steps — the arithmetic stays "polynomial time" in the number of operations, but each individual number becomes enormous.
  • The fix: work modulo a prime. Compute the GCD over the integers modulo a well-chosen prime pp instead of over the rationals; the coefficients then stay bounded by pp, and the true GCD can be reconstructed from one or more of these small, exact computations.
  • The fix: subresultant PRS. A refinement of the Euclidean algorithm called the subresultant polynomial remainder sequence divides out common factors at every step by construction, keeping the coefficients close to their smallest possible size without ever leaving exact arithmetic.

So the shape of Euclid's algorithm survives the jump from integers to polynomials perfectly — what changes is the bookkeeping needed to keep the numbers involved from spiraling out of control.

Where It Matters

Finding what two polynomials have in common is not just a classroom exercise — it is a small workhorse hiding inside a surprising number of tools:

  • Simplifying rational functions: to reduce P(x)Q(x)\frac{P(x)}{Q(x)} to lowest terms, divide both PP and QQ by gcd⁡(P,Q)\gcd(P, Q) — the exact same move as reducing 68\frac{6}{8} to 34\frac{3}{4}.
  • Finding repeated roots: a polynomial f(x)f(x) has a repeated root exactly where f(x)f(x) and its derivative f′(x)f'(x) share a common factor, so gcd⁡(f,f′)\gcd(f, f') pinpoints repeated roots without solving the equation at all.
  • Error-correcting codes: decoding Reed–Solomon codes (used in QR codes, CDs, and deep-space communication) relies on a variant of the Euclidean algorithm on polynomials to recover the original message from a corrupted signal.
  • Computer algebra systems: every system that simplifies symbolic expressions — from graphing calculators to Gröbner basis engines — leans on a fast, numerically careful polynomial GCD as one of its most-used primitives.

It is the same idea as the plain integer GCD, just promoted one level up, from numbers to formulas.

Conclusion

The polynomial GCD is a small proof that good ideas generalize. Euclid never saw an xx in his algorithm, yet "divide, take the remainder, repeat" transfers to polynomials almost without changing a word — only the notion of "smaller" shifts from magnitude to degree.

What falls out of that transfer is genuinely useful: a fast way to spot the roots two polynomials share, to reduce a messy fraction of formulas to its simplest form, and — with a little extra care about exploding coefficients — a building block for the computer algebra systems and error-correcting codes running quietly behind your calculator, your CDs, and your QR codes.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/gcd-polynomials/Content licensed under CC BY-NC 4.0.