Competitive Mathematics: Factorization

Polynomial factorization is a search for structure: common factors, repeated expressions, roots, or symmetries that turn a sum into a product. Before choosing a method, specify which coefficients the factors may have. A polynomial can be irreducible over one field and reducible over another.

1. The coefficient domain

For a field $F$ , a nonconstant polynomial $P\in F[x]$ is reducible over $F$ if $P=AB$ with $A,B\in F[x]$ both of positive degree. Otherwise it is irreducible. A complete factorization expresses a nonzero polynomial as a nonzero constant times irreducible polynomials. Over a field, it is unique up to the order of the factors and multiplication of factors by nonzero constants.

The integers $\mathbb Z$ form a ring, not a field. For an integer polynomial, first extract its content, the greatest common divisor of its coefficients. The remaining polynomial is primitive. Gauss's lemma says that a primitive integer polynomial has a factorization into positive-degree rational polynomials if and only if it has one into positive-degree integer polynomials.

For example,

x^2-2=(x-\sqrt2)(x+\sqrt2)

over $\mathbb R$ , but is irreducible over $\mathbb Q$ . Similarly, $x^2+1$ is irreducible over $\mathbb R$ and splits over $\mathbb C$ as $(x-i)(x+i)$ .

Every nonconstant univariate complex polynomial splits into linear factors. Every univariate real polynomial splits into real linear factors and irreducible real quadratics. This statement does not extend unchanged to multivariate polynomials.

Unless a different domain is stated, the examples below seek positive-degree factors over $\mathbb Q$ and display integer coefficients where possible.

2. Identities worth recognizing

Several identities recur because they reveal cancellation:

\begin{aligned} a^2-b^2&=(a-b)(a+b),\\ a^3-b^3&=(a-b)(a^2+ab+b^2),\\ a^3+b^3&=(a+b)(a^2-ab+b^2),\\ a^3+b^3+c^3-3abc&=(a+b+c)(a^2+b^2+c^2-ab-bc-ca). \end{aligned}

For $n\ge1$ ,

a^n-b^n=(a-b)\sum_{k=0}^{n-1}a^{n-1-k}b^k.

For odd $n$ ,

a^n+b^n=(a+b)\sum_{k=0}^{n-1}(-1)^k a^{n-1-k}b^k.

These follow directly by multiplication: all intermediate terms cancel. They do not require the polynomial remainder theorem.

A useful fourth-power identity is Sophie Germain's:

a^4+4b^4=(a^2+2b^2-2ab)(a^2+2b^2+2ab).

It follows by writing $a^4+4b^4=(a^2+2b^2)^2-(2ab)^2$ . For example,

64a^4+1=(8a^2-4a+1)(8a^2+4a+1).

Recognition should suggest a factorization; expansion should verify it.

3. Undetermined coefficients

For a monic quadratic,

x^2+bx+c=(x+r)(x+s)

requires $r+s=b$ and $rs=c$ . Thus $x^2+x-6=(x+3)(x-2)$ .

More generally, a quadratic $Ax^2+Bx+C$ over $\mathbb Q$ , with $A\ne0$ , is reducible precisely when its discriminant $B^2-4AC$ is a square in $\mathbb Q$ . For instance, $x^2+x-7$ has discriminant $29$ , so it is irreducible over $\mathbb Q$ , while over $\mathbb R$ it factors as

\left(x+\frac{1-\sqrt{29}}2\right) \left(x+\frac{1+\sqrt{29}}2\right).

A rational coefficient does not obstruct factorization. For example,

\frac{x^2}{3}+\frac{x}{3}-2=\frac13(x+3)(x-2).

The original expression belongs to $\mathbb Q[x]$ , not $\mathbb Z[x]$ ; clearing denominators makes the integer calculation available.

A quadratic in two variables

Consider

P=x^2-3xy-10y^2+x-19y-6.

Its homogeneous quadratic part factors as $(x+2y)(x-5y)$ . Try

P=(x+2y+r)(x-5y+s).

Matching the remaining coefficients gives

r+s=1,\qquad2s-5r=-19,\qquad rs=-6.

The first two equations give $r=3$ , $s=-2$ , and these also satisfy the third. Hence

P=(x+2y+3)(x-5y-2).

All coefficient conditions must be checked. Satisfying only the highest-degree terms does not establish a factorization.

4. Substitution and completing a square

A substitution is useful when the same expression occurs repeatedly. It should simplify the structure, and the answer must eventually be expressed in the original variables.

For $y=x^2$ ,

x^4+5x^2-6=(y+6)(y-1)=(x^2+6)(x+1)(x-1).

For $f=x^2+5x-6$ ,

\begin{aligned} f^2+5f-6&=(f+6)(f-1)\\ &=(x^2+5x)(x^2+5x-7)\\ &=x(x+5)(x^2+5x-7). \end{aligned}

The last quadratic has discriminant $53$ , so this is complete over $\mathbb Q$ .

Another expression with the same substitution is

\begin{aligned} x^2+5xf-6f^2&=(x+6f)(x-f)\\ &=(6x^2+31x-36)(-x^2-4x+6). \end{aligned}

Their discriminants, $1825$ and $40$ , are not rational squares, so neither quadratic splits over $\mathbb Q$ .

Four consecutive factors

Pair the outer and inner factors:

\begin{aligned} x(x+1)(x+2)(x+3)+1 &=(x^2+3x)(x^2+3x+2)+1\\ &=(x^2+3x+1)^2. \end{aligned}

The choice $y=x^2+3x$ leaves $y(y+2)+1=(y+1)^2$ . The identity supplies the proof; an expectation that a contest problem “must factor nicely” does not.

A substitution may reveal irreducibility

For $x^4+(x-8)^4$ , center the expression by setting $y=x-4$ :

x^4+(x-8)^4=2(y^4+96y^2+256).

Over $\mathbb R$ ,

y^4+96y^2+256 =(y^2+48-32\sqrt2)(y^2+48+32\sqrt2).

Both constants are positive, so these are irreducible real quadratics. Over $\mathbb Q$ , however, the quartic is irreducible. Here is a proof.

It is positive for every real $y$ , so it has no rational linear factor. If it factored over $\mathbb Q$ , it would have the monic quadratic factorization

(y^2+ay+b)(y^2-ay+d).

Coefficient comparison gives $b+d-a^2=96$ , $a(d-b)=0$ , and $bd=256$ . If $a=0$ , then $b,d=48\pm32\sqrt2$ , which are not rational. Otherwise $d=b$ , so $b=\pm16$ and $a^2=2b-96<0$ , again impossible over $\mathbb Q$ .

The affine substitution is invertible over $\mathbb Q$ , so it preserves reducibility. Finding real factors did not answer the rational factorization problem; the domain distinction was essential.

5. Roots, division, and the rational root theorem

For a polynomial over a field,

P(x)=(x-a)Q(x)+P(a).

Therefore $P(a)=0$ if and only if $x-a$ divides $P$ . Polynomial division finds the quotient.

Now let $P=a_nx^n+\cdots+a_0\in\mathbb Z[x]$ , with $a_na_0\ne0$ . If $p/q$ is a rational root in lowest terms and $q>0$ , then

p\mid a_0,\qquad q\mid a_n.

To prove this, multiply $P(p/q)=0$ by $q^n$ . Reducing the resulting integer equality modulo $p$ shows $p\mid a_0q^n$ ; coprimality gives $p\mid a_0$ . Reducing modulo $q$ similarly gives $q\mid a_np^n$ , hence $q\mid a_n$ .

If $a_0=0$ , first remove factors of $x$ . For a monic integer polynomial with nonzero constant term, every rational root is an integer divisor of that term.

For example,

\begin{aligned} x^4+10x^3+18x^2-35x &=x(x^3+10x^2+18x-35)\\ &=x(x+5)(x^2+5x-7). \end{aligned}

The remaining quadratic has discriminant $53$ . Checking rational roots is a complete irreducibility test for degree two or three, but not for degree four or higher: a quartic can split into two quadratics without having any rational roots.

6. Roots of unity and cyclotomic factors

A primitive $n$ th root of unity has multiplicative order $n$ . The cyclotomic polynomial $\Phi_n(x)$ has exactly these primitive roots, and

x^n-1=\prod_{d\mid n}\Phi_d(x).

Over $\mathbb Q$ , each $\Phi_n$ is irreducible. This is a theorem, not a consequence of merely listing its complex roots.

For a primitive cube root $\omega$ , we have $\omega^3=1$ and $\omega^2+\omega+1=0$ . Consider

P(x)=x^5+x^4+x^2+x+2.

Substituting $\omega$ gives $P(\omega)=2(\omega^2+\omega+1)=0$ . Since $P$ has rational coefficients and the minimal polynomial of $\omega$ over $\mathbb Q$ is $x^2+x+1$ , that quadratic divides $P$ . Division gives

P(x)=(x^2+x+1)(x^3-x+2).

The cubic has no roots among $\pm1,\pm2$ , so it is irreducible over $\mathbb Q$ . The coefficient field matters: if $P$ had arbitrary complex coefficients, one root $\omega$ would only force the linear factor $x-\omega$ .

A related example is

\begin{aligned} x^8+x^4+1 &=(x^4+x^2+1)(x^4-x^2+1)\\ &=(x^2+x+1)(x^2-x+1)(x^4-x^2+1)\\ &=\Phi_3(x)\Phi_6(x)\Phi_{12}(x). \end{aligned}

Its degree does not tell us whether it has rational roots. The cyclotomic identification establishes that these displayed factors are irreducible over $\mathbb Q$ .

7. Eisenstein's criterion and reduction modulo a prime

Some methods prove that further factorization is impossible.

Eisenstein's criterion. Let $P=a_nx^n+\cdots+a_0\in\mathbb Z[x]$ . If a prime $p$ satisfies

p\nmid a_n,\qquad p\mid a_i\ (0\le i<n),\qquad p^2\nmid a_0,

then $P$ is irreducible over $\mathbb Q$ . For $x^5+5x^3+10$ , choose $p=5$ : the leading coefficient is not divisible by $5$ , every other coefficient is, and $25$ does not divide $10$ .

For a primitive polynomial, the proof uses Gauss's lemma. Any positive-degree integer factors retain their degrees modulo $p$ and multiply to a nonzero multiple of $x^n$ . Each reduced factor must be a monomial, so both original constant terms are divisible by $p$ , contradicting $p^2\nmid a_0$ . Removing content handles the general statement. Conrad's irreducibility notes give detailed proofs of these tests.

Reduction modulo $p$ . If $p$ does not divide the leading coefficient and the reduction $\overline P\in\mathbb F_p[x]$ is irreducible, then $P$ is irreducible over $\mathbb Q$ . One suitable prime proves the result; this is not a probabilistic inference from several primes.

For example, $x^3+x+1$ has neither $0$ nor $1$ as a root modulo $2$ . A reducible cubic over a field must have a linear factor, so its reduction is irreducible and the original is irreducible over $\mathbb Q$ .

The converse fails: $x^2+1$ is irreducible over $\mathbb Q$ but reduces to $(x+1)^2$ modulo $2$ . Some rationally irreducible polynomials even reduce to reducible polynomials at every prime; see Conrad's example.

Hensel lifting refines suitable modular factorizations to higher prime powers or to $p$ -adic factors. It does not guarantee that those individual factors are integer polynomials. Algorithms over $\mathbb Q$ need additional reconstruction and verification steps.

8. Symmetric and alternating polynomials

A symmetric polynomial is unchanged by permuting its variables. An alternating polynomial changes sign under each transposition. These are different properties, and the distinction helps predict factors.

For example,

P=a^3(b-c)+b^3(c-a)+c^3(a-b)

is alternating. Setting any two variables equal makes it zero. Polynomial division, treating one variable as the polynomial variable and the others as coefficients, then shows that $a-b$ , $b-c$ , and $c-a$ each divide $P$ .

These are distinct prime linear factors in $\mathbb Q[a,b,c]$ , so their product divides $P$ . Individual divisibility would not imply product divisibility for arbitrary overlapping factors.

Let $\Delta=(a-b)(b-c)(c-a)$ . Since $P$ has degree four and $\Delta$ degree three, the quotient is homogeneous of degree one. Both change sign under transpositions, so their quotient is symmetric and must equal $k(a+b+c)$ . Evaluating at $(a,b,c)=(1,2,0)$ gives $k=-1$ . Hence

P=-(a+b+c)(a-b)(b-c)(c-a).

A symmetric cubic

The elementary symmetric polynomials are

e_1=a+b+c,\qquad e_2=ab+bc+ca,\qquad e_3=abc.

They provide a convenient language for symmetric expressions. For instance,

a^3+b^3+c^3-3abc=e_1(e_1^2-3e_2).

The quadratic factor equals

a^2+b^2+c^2-ab-bc-ca =\frac12\big((a-b)^2+(b-c)^2+(c-a)^2\big).

It vanishes over $\mathbb R$ exactly on the line $a=b=c$ . It cannot be a product of two real linear forms, whose zero sets would include planes. Thus it is irreducible over $\mathbb R$ , though it splits over $\mathbb C$ as

(a+\omega b+\omega^2c)(a+\omega^2b+\omega c).

A second useful cubic identity is

\begin{aligned} &a^2(a-b-c)+b^2(b-c-a)+c^2(c-a-b)+2abc\\ &\qquad=(a-b-c)(b-c-a)(c-a-b). \end{aligned}

Substitution into any proposed linear factor and final expansion verify it.

Splitting by homogeneous degree

Consider the nonhomogeneous cyclic expression

\begin{aligned} P(x,y,z)={}&(y^2-z^2)(1+xy)(1+xz)\\ &+(z^2-x^2)(1+yz)(1+yx)\\ &+(x^2-y^2)(1+zx)(1+zy). \end{aligned}

The degree-two terms cancel. Writing $\Delta=(x-y)(y-z)(z-x)$ , the degree-five terms sum to $xyz\Delta$ and the degree-four terms sum to $(x+y+z)\Delta$ . Both identities follow by expansion, or by the alternating-polynomial argument above. Therefore

P=(xyz+x+y+z)(x-y)(y-z)(z-x).

Finally, some apparently complicated expressions are zero polynomials. Put $A=(x+y+z)^2$ , $B=x^2+y^2+z^2$ , and $e_2=xy+yz+zx$ . Since $A-B=2e_2$ ,

A^2-B^2-2e_2(A+B)=(A+B)(A-B-2e_2)=0.

Identifying zero is different from finding a complete irreducible factorization of a nonzero polynomial.

A practical order of attack

First specify the coefficient domain and remove common factors. Then inspect the degree, missing powers, repeated expressions, and symmetries. Try a substitution or a small set of coefficient comparisons before expanding a large expression. Use root tests and irreducibility criteria when the remaining question is whether further factors exist.

At the end, expand the proposed product and check whether each remaining factor is irreducible in the requested domain. A plausible pattern is a starting point for a proof, not a substitute for one.