Introduction

Take the polynomial p(x)=(x−1)2(x+2)3p(x) = (x-1)^2(x+2)^3. Multiplied out it is just a string of coefficients — x5+4x4+x3−10x2−4x+8x^5+4x^4+x^3-10x^2-4x+8 — with no obvious sign that two of its roots are repeated. Finding the actual roots 11 and −2-2 can be genuinely hard work. But there is a much easier question hiding in plain sight: which roots repeat, and how many times, without solving for a single root?

The trick uses calculus, of all things. A repeated root of p(x)p(x) is also a root of its derivative p′(x)p'(x) — that is exactly what "repeated" means graphically: the curve touches zero and doubles back instead of crossing it. So a repeated factor (x−r)k(x-r)^k of pp leaves behind a (x−r)k−1(x-r)^{k-1} inside p′(x)p'(x).

That means the greatest common divisor of p(x)p(x) and p′(x)p'(x) captures every repeated factor at once — computed with nothing more exotic than polynomial long division run in a loop, exactly like Euclid's algorithm for ordinary integers.

Try It

Below is p(x)=(x−1)2(x+2)3p(x) = (x-1)^2(x+2)^3, a degree-5 polynomial with a double root at x=1x=1 and a triple root at x=−2x=-2. Step through the process: differentiate, then compute the gcd of pp and p′p', then divide it out.

<p class="hint">p(x) = (x-1)²(x+2)³ has a double root at x = 1 and a triple root at x = -2. Step through the pipeline to strip the repeats using nothing but a derivative, a gcd, and a division.</p>
<div class="poly-row"><span class="poly-label">p(x) =</span><span class="poly-expr" id="expr-p"></span></div>
<div class="poly-row" id="row-dp"><span class="poly-label">p’(x) =</span><span class="poly-expr" id="expr-dp">—</span></div>
<div class="poly-row" id="row-gcd"><span class="poly-label">gcd =</span><span class="poly-expr" id="expr-gcd">—</span></div>
<div class="poly-row" id="row-sf"><span class="poly-label">squarefree =</span><span class="poly-expr" id="expr-sf">—</span></div>
<div class="axis-wrap">
  <div class="axis" id="axis-before"></div>
  <div class="axis-title">Roots of p(x), with multiplicity</div>
  <div class="axis" id="axis-after"></div>
  <div class="axis-title">Roots after dividing out the gcd</div>
</div>
<div class="status" id="status">Press "Differentiate" to begin.</div>
<div class="btns">
  <button id="step-deriv" type="button">Differentiate</button>
  <button id="step-gcd" type="button">Compute gcd</button>
  <button id="step-divide" type="button">Divide it out</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; }
.poly-row { display: flex; gap: .5rem; align-items: baseline; font: 600 15px ui-monospace, monospace;
            margin: .15rem 0; opacity: .35; transition: opacity .25s; }
.poly-row.active { opacity: 1; }
.poly-label { min-width: 8ch; color: #1d3557; font-family: system-ui, sans-serif; font-weight: 700; font-size: 13px; }
.poly-expr { color: #222; }
.axis-wrap { margin: .9rem 0 .6rem; }
.axis-title { font-size: .78rem; color: #555; margin: .15rem 0 .5rem; }
.axis { position: relative; height: 34px; border-bottom: 2px solid #cdd9e3; margin: 0 6px; }
.tick { position: absolute; bottom: -3px; width: 2px; height: 8px; background: #adb1b8; }
.root-dot { position: absolute; bottom: -11px; width: 22px; height: 22px; border-radius: 50%;
            display: flex; align-items: center; justify-content: center; transform: translateX(-50%);
            font: 700 11px ui-monospace, monospace; color: #fff; background: #e63946; border: 2px solid #c92f3c;
            transition: left .4s ease; }
.root-dot.mult1 { background: #0a7d33; border-color: #086e2c; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.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 i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Squarefree factorization demo: strip repeated roots from a fixed polynomial
// using only its derivative and a polynomial gcd — no root-finding involved.
// p(x) = (x-1)^2 (x+2)^3, low-to-high coefficients
const P = [8, -4, -10, 1, 4, 1];

// Drop trailing near-zero high-degree coefficients so degree stays accurate.
function trim(p){ p = p.slice(); while (p.length > 1 && Math.abs(p[p.length-1]) < 1e-9) p.pop(); return p; }

// Derivative of p(x) = sum a_i x^i is sum i*a_i x^(i-1), coefficient-wise.
function deriv(p){ const d = []; for (let i=1;i<p.length;i++) d.push(i*p[i]); return trim(d.length?d:[0]); }

// Polynomial long division, returning quotient and remainder (low-to-high coeffs).
function divMod(a,b){
  a = trim(a.slice()); b = trim(b.slice());
  let rem = a.slice();
  const degb = b.length-1;
  const dega = a.length-1;
  const quot = new Array(Math.max(dega-degb+1,0)).fill(0);
  while (true){
    rem = trim(rem);
    const degr = rem.length-1;
    if (degr < degb || (rem.length===1 && Math.abs(rem[0])<1e-9)) break;
    const coef = rem[degr]/b[degb];
    const shift = degr-degb;
    quot[shift] = coef;
    for (let i=0;i<=degb;i++) rem[shift+i] -= coef*b[i];
  }
  return { quot: trim(quot), rem: trim(rem) };
}

// Euclidean algorithm for polynomials, normalized to a monic result.
function gcd(a,b){
  a = trim(a.slice()); b = trim(b.slice());
  while (!(b.length===1 && Math.abs(b[0])<1e-9)){
    const { rem } = divMod(a,b);
    a = b; b = trim(rem);
  }
  const lc = a[a.length-1];
  return a.map(x => Math.round((x/lc)*1e6)/1e6);
}

// Render a coefficient array (low-to-high) as a human-readable polynomial string.
function fmtPoly(p){
  const deg = p.length-1;
  const terms = [];
  for (let i=deg;i>=0;i--){
    const c = p[i];
    if (Math.abs(c) < 1e-9) continue;
    const ac = Math.abs(c);
    let t;
    if (i===0) t = String(ac);
    else if (i===1) t = (ac===1?'':String(ac)) + 'x';
    else t = (ac===1?'':String(ac)) + 'x^' + i;
    terms.push((c<0 ? '− ' : (terms.length ? '+ ' : '')) + t);
  }
  return terms.join(' ') || '0';
}

// Known roots of P and their multiplicities, used only to draw the number line.
// The two real roots of P and their multiplicity in P, hardcoded because
// this demo is about *separating* known multiplicities, not root-finding.
const ROOTS = [ { x: -2, mult: 3 }, { x: 1, mult: 2 } ];
const SF_ROOTS = [ { x: -2, mult: 1 }, { x: 1, mult: 1 } ];

function drawAxis(elId, roots){
  const el = document.getElementById(elId);
  el.innerHTML = '';
  const min = -4, max = 3;
  const toPct = x => ((x - min) / (max - min)) * 100;
  for (let t = Math.ceil(min); t <= Math.floor(max); t++){
    const tick = document.createElement('div');
    tick.className = 'tick';
    tick.style.left = toPct(t) + '%';
    el.appendChild(tick);
  }
  roots.forEach(r => {
    const dot = document.createElement('div');
    dot.className = 'root-dot' + (r.mult === 1 ? ' mult1' : '');
    dot.style.left = toPct(r.x) + '%';
    dot.textContent = r.mult > 1 ? ('×' + r.mult) : '1';
    dot.title = i18nFmt('root x = %x%, multiplicity %m%', { x: r.x, m: r.mult });
    el.appendChild(dot);
  });
}

let stage = 0; // 0=start, 1=derivative shown, 2=gcd shown, 3=divided
let DP = null, G = null, SF = null;

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

function render(){
  document.getElementById('expr-p').textContent = fmtPoly(P);
  document.getElementById('row-dp').classList.toggle('active', stage >= 1);
  document.getElementById('row-gcd').classList.toggle('active', stage >= 2);
  document.getElementById('row-sf').classList.toggle('active', stage >= 3);
  document.getElementById('expr-dp').textContent = DP ? fmtPoly(DP) : '—';
  document.getElementById('expr-gcd').textContent = G ? fmtPoly(G) : '—';
  document.getElementById('expr-sf').textContent = SF ? fmtPoly(SF) : '—';
  drawAxis('axis-before', ROOTS);
  drawAxis('axis-after', stage >= 3 ? SF_ROOTS : []);
  document.getElementById('step-deriv').disabled = stage >= 1;
  document.getElementById('step-gcd').disabled = stage < 1 || stage >= 2;
  document.getElementById('step-divide').disabled = stage < 2 || stage >= 3;
}

function stepDeriv(){
  DP = deriv(P);
  stage = 1;
  setStatus('Derivative computed. Now take the gcd of p(x) and p’(x).', 'info');
  render();
}
function stepGcd(){
  G = gcd(P, DP);
  stage = 2;
  setStatus(i18nFmt('gcd(p, p’) has degree %deg% — that is exactly the repeated part of p. Now divide it out.', { deg: G.length - 1 }), 'info');
  render();
}
function stepDivide(){
  SF = divMod(P, G).quot;
  stage = 3;
  setStatus('Done. Each root now appears exactly once — this is the squarefree part of p(x).', 'ok');
  console.log('Squarefree part obtained via gcd(p, p’), no root-finding used.');
  render();
}
function resetAll(){
  DP = null; G = null; SF = null; stage = 0;
  setStatus('Press "Differentiate" to begin.', '');
  render();
}

document.getElementById('step-deriv').addEventListener('click', stepDeriv);
document.getElementById('step-gcd').addEventListener('click', stepGcd);
document.getElementById('step-divide').addEventListener('click', stepDivide);
document.getElementById('reset').addEventListener('click', resetAll);
render();
Result
Console

Watch the root plot as you go. The starting polynomial shows only two distinct dots, doubled and tripled up. After dividing out the gcd, the result is x2+x−2=(x−1)(x+2)x^2+x-2=(x-1)(x+2) — the same two roots, but now each appears exactly once. Nothing was solved for; the repeats simply fell out of arithmetic on coefficients.

The Real Complexity

This is a solved problem with a clean, fast answer — no open questions here, unlike much of what a site about the limits of computation usually covers.

  • Differentiate. For p(x)=∑i=0naixip(x) = \sum_{i=0}^n a_i x^i, the derivative p′(x)=∑i=1ni aixi−1p'(x) = \sum_{i=1}^n i\,a_i x^{i-1} costs O(n)O(n) arithmetic operations — just multiply each coefficient by its exponent.
  • Take the gcd. Computing g(x)=gcd⁡(p(x),p′(x))g(x) = \gcd(p(x), p'(x)) with the polynomial Euclidean algorithm costs O(n2)O(n^2) arithmetic operations over a field, the same complexity class as Euclid's algorithm on integers, just with polynomial long division replacing ordinary remainder.
  • Divide it out. One more polynomial long division, p(x)/g(x)p(x) / g(x), produces p(x)p(x)'s squarefree part: the same roots, each with multiplicity exactly 11.
  • No roots required. Nothing above ever asks "what is a root of pp" — it is pure symbolic manipulation of coefficients, which is precisely why it stays fast even when the actual roots are irrational, complex, or otherwise unpleasant to compute.

The refined version used in practice, Yun's algorithm (1976), goes further: it peels apart which factor is squared, cubed, and so on, in a total of O(n2)O(n^2) operations rather than repeating the whole gcd from scratch for every power. Over a field of characteristic 00 (like the rationals) this always works; over a finite field of characteristic pp there is one subtlety — a factor raised to a multiple of pp can vanish under differentiation and needs a separate check — but the core gcd idea survives intact.

Where It Matters

Squarefree factorization rarely gets its own headline, because it is almost always step one of something bigger:

  • Factoring pipelines: algorithms like Berlekamp's factorization over finite fields assume the input is already squarefree — running squarefree factorization first turns a messier problem into the clean case those algorithms were designed for.
  • Computer algebra systems: Maple, Mathematica and SageMath all call a squarefree-factorization routine before attempting full factorization, since it is far cheaper and immediately reveals the multiplicity structure.
  • Symbolic integration: the Rothstein-Trager method and other algorithms for integrating rational functions in closed form rely on separating squarefree parts of the denominator.
  • Root-finding stability: numerical root-finders (like companion-matrix eigenvalue methods) behave far better on squarefree polynomials, since repeated roots are numerically unstable to pin down precisely.

It's unglamorous, but it's the reason bigger, harder algorithms downstream get to assume a friendlier input.

Conclusion

Squarefree factorization is a small, elegant fact hiding in plain sight: differentiation and division are all you need to see which roots of a polynomial repeat, long before you know what those roots actually are. The gcd of p(x)p(x) and p′(x)p'(x) does the sorting for free.

It is a good reminder that not everything on the road to a hard problem is itself hard. Squarefree factorization is the calm, fully solved preprocessing step that every serious factoring algorithm — from Berlekamp's method to a modern computer algebra system — quietly runs first.

Share this article

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

Comments

Loading comments...

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