Kvant Math Problem 16

Consider a polynomial $p(x)$ with integer coefficients that takes the value $1$ at three distinct integers, say $a$, $b$, and $c$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m14s
Source on kvant.digital

Problem

Prove that a polynomial $p(x)$ with integer coefficients, which takes the value 1 for three distinct integer values of $x$, cannot have any integer roots.

Exploration

Consider a polynomial $p(x)$ with integer coefficients that takes the value $1$ at three distinct integers, say $a$, $b$, and $c$. Denote $p(a) = p(b) = p(c) = 1$. A natural approach is to examine the shifted polynomial $q(x) = p(x) - 1$, which then vanishes at $x = a, b, c$. Therefore, $q(x)$ has three distinct integer roots, so it is divisible by $(x-a)(x-b)(x-c)$ with integer coefficients. Suppose $p(x)$ also has an integer root $r$. Then $q(r) = p(r)-1 = -1$. This forces $(r-a)(r-b)(r-c) = -1$ in integers. The next step is to analyze whether three integers can have a product equal to $-1$ without being one of $a$, $b$, or $c$. Testing small integer examples, if $(r-a)(r-b)(r-c) = -1$, then two of the factors must be $\pm 1$ and the third $\mp 1$. Since $a$, $b$, $c$ are distinct, no permutation of $\pm 1$ differences can be distinct simultaneously. Therefore, the equation has no integer solutions. The key difficulty lies in proving that no integer solution $r$ can exist without assuming the trivial small-number cases; a careful combinatorial argument on integers is needed.

Problem Understanding

The problem asks to prove that a polynomial $p(x)$ with integer coefficients, which takes the value $1$ for three distinct integers, cannot itself vanish at any integer. This is a Type B problem because it asks for a proof of a universal statement. The core difficulty is showing that $p(r) = 0$ cannot occur, even though $p(a) = p(b) = p(c) = 1$, which requires a precise analysis of integer divisibility and the product of three integers differing by distinct integers. The insight is that shifting by $1$ gives a polynomial divisible by three distinct linear factors with integer coefficients, and an integer root would force their product to equal $-1$, which is impossible.

Proof Architecture

Lemma 1: If $p(x)$ has integer coefficients, then for any integers $r$, $a$, $b$, $c$, the quantity $(r-a)(r-b)(r-c)$ divides $p(r)-p(a)$ in integers. Sketch: Use the fact that $p(x) - p(a)$ is divisible by $x-a$ with integer quotient and apply it recursively.

Lemma 2: For distinct integers $a$, $b$, $c$, there exists no integer $r$ such that $(r-a)(r-b)(r-c) = \pm 1$. Sketch: Consider the absolute values of differences; three distinct integers cannot have three pairwise differences whose product is $\pm 1$.

Main Claim: No integer $r$ satisfies $p(r) = 0$. Sketch: Let $q(x) = p(x)-1$ and use Lemmas 1 and 2 to show that $q(r) = -1$ has no integer solutions.

The hardest step is Lemma 2 because it requires careful combinatorial reasoning about integers, and a careless argument could miss a small example like $0$, $1$, $-1$.

Solution

Let $a$, $b$, $c$ be three distinct integers such that $p(a) = p(b) = p(c) = 1$. Define the polynomial

$q(x) = p(x) - 1.$

Then $q(x)$ has integer coefficients and satisfies

$q(a) = q(b) = q(c) = 0.$

Hence $q(x)$ is divisible by the product of linear factors corresponding to these roots:

$q(x) = (x-a)(x-b)(x-c) \cdot s(x),$

where $s(x)$ is a polynomial with integer coefficients.

Suppose, for the sake of contradiction, that $p(x)$ has an integer root $r$. Then $p(r) = 0$, so $q(r) = p(r)-1 = -1$. Substituting into the factorization gives

$(r-a)(r-b)(r-c) \cdot s(r) = -1.$

Since $r$, $a$, $b$, $c$ are integers, $s(r)$ is also an integer. Therefore $(r-a)(r-b)(r-c)$ must be a divisor of $-1$ in integers. The only integer divisors of $-1$ are $1$ and $-1$. Hence

$(r-a)(r-b)(r-c) = \pm 1.$

Consider three distinct integers $r-a$, $r-b$, $r-c$. If their product is $1$, then the numbers must be a permutation of $(1, 1, 1)$, $(-1, -1, 1)$, or similar combinations to give $1$. All possibilities require at least two of the differences to be equal, but $a$, $b$, $c$ are distinct, so $r-a$, $r-b$, $r-c$ are distinct. Similarly, if their product is $-1$, the absolute values must still include at least one repetition to satisfy integer multiplication. Therefore, no integer $r$ exists such that $(r-a)(r-b)(r-c) = \pm 1$.

This contradiction shows that no integer $r$ can satisfy $p(r) = 0$.

This completes the proof.

∎

Verification of Key Steps

In Lemma 2, the claim that three distinct integers cannot multiply to $\pm 1$ was verified by enumerating all possibilities for small integers: the absolute values must be $1$, giving three numbers among ${-1, 1}$, but any three distinct integers cannot all lie in this set. The argument also holds for larger integers because any integer with absolute value greater than $1$ would make the product exceed $1$ in absolute value. Another delicate step is the factorization $q(x) = (x-a)(x-b)(x-c)s(x)$ with integer coefficients. This is justified because $q(x)$ vanishes at three distinct integers and has integer coefficients, so the quotient $s(x)$ also has integer coefficients by the division algorithm for polynomials over integers.

Alternative Approaches

An alternative approach is to consider the polynomial modulo an integer. For instance, reducing modulo $p$ for a prime $p$ allows one to analyze congruences: if $p(r) = 0$, then $p(r) \equiv 0 \pmod{r-a}$, $r-b$, $r-c$, forcing a contradiction in modular arithmetic. This method is shorter in appearance but requires familiarity with divisibility properties modulo primes. The main approach is preferable because it relies solely on elementary integer arithmetic and the basic factor theorem, making it fully accessible to a high school audience.