The Polynomial GCD

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.

Below are two polynomials, $A(x)$ and $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">{{hint_para}}</p>
<div class="pair" id="pair"></div>
<div class="status" id="status">{{status_start}}</div>
<div class="log" id="log"></div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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

The algorithm itself is fast: with polynomials of degree at most $n$, each division reduces the degree by at least one, so the process terminates in at most $n$ steps, and each step costs $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 $p$ instead of over the rationals; the coefficients then stay bounded by $p$, 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.

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 $\frac{P(x)}{Q(x)}$ to lowest terms, divide both $P$ and $Q$ by $\gcd(P, Q)$ — the exact same move as reducing $\frac{6}{8}$ to $\frac{3}{4}$.
• Finding repeated roots: a polynomial $f(x)$ has a repeated root exactly where $f(x)$ and its derivative $f'(x)$ share a common factor, so $\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.

The polynomial GCD is a small proof that good ideas generalize. Euclid never saw an $x$ 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.