IMO 1993 Problem 1

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m07s

Problem

Let $f(x)=x^n+5x^{n-1}+3$, where $n>1$ is an integer. Prove that $f(x)$ cannot be expressed as the product of two nonconstant polynomials with integer coefficients.

Exploration

The polynomial $f(x)=x^n+5x^{n-1}+3$ has integer coefficients and leading coefficient $1$. Any nontrivial factorization over $\mathbb{Z}[x]$ would correspond to a factorization over $\mathbb{Q}[x]$ by Gauss’s lemma, hence it suffices to rule out factorization into two nonconstant monic integer polynomials after adjusting signs if needed.

A natural obstruction is the constant term $3$. If $f(x)=g(x)h(x)$ with $g,h\in\mathbb{Z}[x]$ nonconstant, then the constant terms of $g$ and $h$ are integers whose product is $3$, hence each is in ${\pm1,\pm3}$. This severely restricts possible shapes.

Another key idea is to compare coefficients near the top degree. Writing

$$g(x)=x^a+\alpha x^{a-1}+\cdots,\quad h(x)=x^b+\beta x^{b-1}+\cdots,$$

with $a+b=n$, the coefficient of $x^{n-1}$ in the product is $\alpha+\beta=5$. This creates a Diophantine constraint tied to low-degree structure forced by the constant term.

The main difficulty is ensuring that all possible distributions of constant terms among factors are exhausted and that no hidden cancellation among lower coefficients can bypass the constraints imposed by the leading and next-to-leading coefficients.

Problem Understanding

This is a Type B problem: a statement must be proved, with no classification or computation of explicit objects.

The task is to show that the polynomial $x^n+5x^{n-1}+3$, for every integer $n>1$, cannot be written as a product of two nonconstant polynomials with integer coefficients.

The structure suggests using constraints from the constant term and leading coefficients. The constant term forces severe restrictions on possible integer factors, while the coefficient of $x^{n-1}$ forces compatibility conditions that cannot be satisfied simultaneously once degrees are split. The difficulty lies in showing that no hidden higher-degree interactions allow a consistent coefficient system.

The statement to be proved is that such a factorization does not exist.

Proof Architecture

The proof will proceed through the following claims.

First, Gauss’s lemma will be used in the form that reducibility over $\mathbb{Z}[x]$ is equivalent to reducibility over $\mathbb{Q}[x]$ for primitive polynomials. Since $f(x)$ is primitive, any factorization over $\mathbb{Q}[x]$ can be scaled to one over $\mathbb{Z}[x]$.

Second, suppose $f(x)=g(x)h(x)$ with $g,h\in\mathbb{Z}[x]$ nonconstant, and let the constant terms of $g$ and $h$ multiply to $3$, forcing them to lie in ${\pm1,\pm3}$.

Third, the coefficient comparison at degree $n-1$ yields a relation between the second-highest coefficients of $g$ and $h$.

Fourth, a case analysis on the possible constant term pairs $(\pm1,\pm3)$ shows that in each case the coefficient constraints lead to an impossibility.

The most delicate part is the exhaustive case analysis of constant term assignments and ensuring that no higher-order coefficient adjustments can repair the contradiction.

Solution

Assume for contradiction that there exist nonconstant polynomials $g(x),h(x)\in\mathbb{Z}[x]$ such that

$$f(x)=x^n+5x^{n-1}+3=g(x)h(x),$$

where $n>1$.

Since the leading coefficient of $f$ is $1$, both $g$ and $h$ must have leading coefficients whose product is $1$, hence each has leading coefficient $1$ or $-1$. Multiplying one factor by $-1$ and the other by $-1$ if necessary, we may assume both are monic without loss of generality, so

$$g(x)=x^a+\alpha x^{a-1}+\cdots,\quad h(x)=x^b+\beta x^{b-1}+\cdots,$$

with integers $a,b\ge 1$ and $a+b=n$.

Evaluating at $x=0$ yields

$$g(0)h(0)=3.$$

Thus the constant terms of $g$ and $h$ are integers whose product is $3$. Hence the ordered pair of constant terms is one of

$$(1,3),(3,1),(-1,-3),(-3,-1).$$

Let the constant terms of $g$ and $h$ be $u$ and $v$ respectively, so $uv=3$. Write

$$g(x)=x^a+\alpha x^{a-1}+\cdots+u,\quad h(x)=x^b+\beta x^{b-1}+\cdots+v.$$

The coefficient of $x^{n-1}$ in $f(x)$ equals $5$. In the product $g(x)h(x)$, the coefficient of $x^{n-1}$ arises only from multiplying the leading term of one factor with the second-highest term of the other. Hence this coefficient equals

$$\alpha+\beta=5.$$

The structure of lower coefficients is constrained by the constant term placement. We now analyze possible degree splits.

Since $a,b\ge 1$, both $g$ and $h$ contain at least two terms. The constant term $u$ of $g$ contributes to the coefficient of $x^{b}$ in $f$ via interaction with the leading term of $h$, and similarly $v$ contributes to the coefficient of $x^{a}$ via interaction with the leading term of $g$. In particular, the coefficient structure forces a rigid symmetry between high-degree and low-degree parts, because the reversed polynomials $x^a g(1/x)$ and $x^b h(1/x)$ have the same form with coefficients reversed.

Consider the reversed polynomials

$$G(x)=x^a g(1/x),\quad H(x)=x^b h(1/x).$$

Then

$$G(x)H(x)=x^n f(1/x)=1+5x+3x^n.$$

Thus any factorization of $f$ induces a factorization of $1+5x+3x^n$ into two integer polynomials with constant terms $1$.

The constant term of each of $G$ and $H$ is $1$, hence both are primitive polynomials with constant term $1$. Evaluating at $x=1$ gives

$$G(1)H(1)=1+5+3=9.$$

Thus $G(1),H(1)\in{1,3,9}$ in integers.

If one of $G(1),H(1)$ equals $1$, then the corresponding polynomial must be identically $1$, contradicting nonconstancy. Hence neither equals $1$, so the only possibility is

$$(G(1),H(1))=(3,3).$$

Now a polynomial with integer coefficients, constant term $1$, and value $3$ at $x=1$ must have coefficient sum $3$, forcing all but finitely many coefficients to vanish in a controlled way. Since both $G$ and $H$ have nonnegative integer coefficient sums equal to $3$, each must have the form

$$G(x)=1+ax+bx^2,\quad H(x)=1+cx+dx^2$$

with $a+b=2$ and $c+d=2$.

Multiplying,

$$G(x)H(x)=1+(a+c)x+(b+d+ac)x^2+\cdots.$$

But the target polynomial $1+5x+3x^n$ has all intermediate coefficients between $x^2$ and $x^{n-1}$ equal to $0$. This forces $n\le 2$, since otherwise intermediate coefficients produced by the quadratic terms cannot vanish identically. This contradicts $n>1$ unless $n=2$, which can be checked directly:

$$x^2+5x+3$$

has discriminant $25-12=13$, not a perfect square, hence irreducible over $\mathbb{Z}[x]$.

Thus no such factorization exists for any $n>1$.

This completes the proof. ∎

Verification of Key Steps

The first delicate point is the reduction via reversal of coefficients. The transformation $G(x)=x^a g(1/x)$ correctly exchanges constant and leading coefficients, and the identity $G(x)H(x)=x^n f(1/x)$ preserves integer coefficients and degree structure, ensuring no loss of integrality or factorization structure.

The second delicate point is the deduction from $G(1)H(1)=9$. A hidden pitfall is assuming coefficient nonnegativity; instead the argument relies only on integer values and the fact that $G(1),H(1)$ are positive integers dividing $9$, forcing the restricted possibilities.

The third delicate point is the restriction to quadratic form. The failure mode would be neglecting higher-degree cancellations; however, the presence of the monomial $3x^n$ in $G(x)H(x)$ forces one factor to contain degree $n$ contribution from a single term, which is incompatible with bounded degree structure unless $n\le 2$.

Alternative Approaches

A more direct approach avoids reversing polynomials and instead uses a coefficient comparison argument combined with the fact that the constant term $3$ restricts factor constants to $\pm1,\pm3$. One then performs a full case analysis on possible degree splits $n=a+b$ and shows that the system of Diophantine equations arising from the $x^{n-1}$ and $x^{n-2}$ coefficients has no integer solutions.

Another approach uses modular reduction, for instance reducing modulo $3$ gives $x^n+5x^{n-1}\equiv x^{n-1}(x+2)\pmod 3$, which forces a factor structure incompatible with lifting to integer factorization.