Square-free polynomial

In mathematics, a square-free polynomial is a polynomial with no square factors, i.e, $f\; in\; F\; [x]$ is square-free if and only if $b^2\; mid\; f$ for every $b\; in\; F\; [x]$ with non-zero degree. This definition implies that no factors of higher order can exist, either, for if $b^3$ divided the polynomial, then $b^2$ would divide it also. In applications in physics and engineering, a square-free polynomial is much more commonly called a polynomial with no repeated roots.

Any separable polynomial is square-free. Conversely, if the field "F" is perfect, all square-free polynomials over "F" are separable. In particular, if "f" is a square-free polynomial over a perfect field, then the greatest common divisor of "f" and its formal derivative "f" ′ is 1.

A square-free factorization of a polynomial is a factorization into powers of square-free factors, i.e:

:$f(x)\; =\; a\_1(x)\; a\_2(x)^2\; a\_3(x)^3\; cdots\; a\_n(x)^n$

where the $a\_k(x)$ are pairwise coprime square-free polynomials. Clearly, any non-zero polynomial admits a square-free factorization, since it could be factored into irreducible factors and the multiplicity of each irreducible factor counted to determine which $a\_k(x)$ it is part of.

The utility of a square-free factorization is that it is generally easier to compute than a full irreducible factorization. For this reason, square-free factorization is often used as the first step in polynomial factorization or root-finding algorithms.

Over fields of characteristic 0, only differentiation, polynomial division, and GCD calculation (which can be done using the Euclidean algorithm) is required to compute the square-free factorization. Let "f" be a non-zero polynomial, decomposed into square-free factors as above. Consider any irreducible factor "q" of "f": we may write $f=q^kh$, where "k">0 and $q\; mid\; h$. By the product rule,:$f\text{'}=k,q^\{k-1\}q\text{'}h+q^kh\text{'}.$As the characteristic is 0, "q" does not divide "k", "q"′, or "h", thus $q^k\; midgcd(f,f\text{'})$ and $q^\{k-1\}midgcd(f,f\text{'})$. That is, the multiplicity of any irreducible factor in $gcd(f,f\text{'})$ is one less than its multiplicity in "f", so

:$gcd(f,f\text{'})\; =\; a\_2a\_3^2\; cdots\; a\_n^\{n-1\}$ and $frac\{f\}\{gcd(f,f\text{'})\}=\; a\_1a\_2cdots\; a\_n$.

Now, if we compute recursively

:$f\_0=f,$, $f\_1=gcd(f\_0,f\_0\text{'}),$, $f\_2=gcd(f\_1,f\_1\text{'}),$, $f\_3=gcd(f\_2,f\_2\text{'}),$, $dots$

we obtain the polynomials

:$g\_k:=frac\{f\_\{k-1\{f\_k\}=a\_ka\_\{k+1\}cdots\; a\_n$,

from which we recover the square-free factors as $a\_k=frac\{g\_k\}\{g\_\{k+1$.

A modification of this algorithm also works for polynomials over finite fields, or more generally, perfect fields of non-zero characteristic "p", if we know an algorithm to compute "p"-th roots of elements of the field.