Squarefree Factorization

Take the polynomial $p(x) = (x-1)^2(x+2)^3$. Multiplied out it is just a string of coefficients — $x^5+4x^4+x^3-10x^2-4x+8$ — with no obvious sign that two of its roots are repeated. Finding the actual roots $1$ and $-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)$ is also a root of its derivative $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$ of $p$ leaves behind a $(x-r)^{k-1}$ inside $p'(x)$.

That means the greatest common divisor of $p(x)$ and $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.

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

<p class="hint">{{hint_para}}</p>
<div class="poly-row"><span class="poly-label">{{label_p}}</span><span class="poly-expr" id="expr-p"></span></div>
<div class="poly-row" id="row-dp"><span class="poly-label">{{label_dp}}</span><span class="poly-expr" id="expr-dp">—</span></div>
<div class="poly-row" id="row-gcd"><span class="poly-label">{{label_gcd}}</span><span class="poly-expr" id="expr-gcd">—</span></div>
<div class="poly-row" id="row-sf"><span class="poly-label">{{label_sf}}</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">{{title_before}}</div>
  <div class="axis" id="axis-after"></div>
  <div class="axis-title">{{title_after}}</div>
</div>
<div class="status" id="status">{{status_start}}</div>
<div class="btns">
  <button id="step-deriv" type="button">{{btn_deriv}}</button>
  <button id="step-gcd" type="button">{{btn_gcd}}</button>
  <button id="step-divide" type="button">{{btn_divide}}</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; }
.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; }

// Code not found

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 $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.

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) = \sum_{i=0}^n a_i x^i$, the derivative $p'(x) = \sum_{i=1}^n i\,a_i x^{i-1}$ costs $O(n)$ arithmetic operations — just multiply each coefficient by its exponent.
• Take the gcd. Computing $g(x) = \gcd(p(x), p'(x))$ with the polynomial Euclidean algorithm costs $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)$, produces $p(x)$'s squarefree part: the same roots, each with multiplicity exactly $1$.
• No roots required. Nothing above ever asks "what is a root of $p$" — 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(n^2)$ operations rather than repeating the whole gcd from scratch for every power. Over a field of characteristic $0$ (like the rationals) this always works; over a finite field of characteristic $p$ there is one subtlety — a factor raised to a multiple of $p$ can vanish under differentiation and needs a separate check — but the core gcd idea survives intact.

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.

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)$ and $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.