Star problems Advanced ← Back to chapter

Polynomial Division and Roots: Star problems

Ten optional challenges to stretch your reasoning. Work on paper, use hints when you need them, and check the answer or full solution when you are ready. You can skip these problems and continue the course.

1 of 3 stars: Stretch
2 of 3 stars: Challenge
3 of 3 stars: Deep challenge

Stars indicate difficulty within this set.

0 of 10 completed

Progress saved in this browser.

Problem 1 of 10

Problem 1 Two inputs exchange places

Difficulty: 1 of 3 stars, Stretch

A real polynomial $P$ satisfies $P(-2)=3$ and $P(3)=-2$ . Without finding $P$ or expanding its compositions, determine the remainders when $P(P(x))-x$ and $P(P(P(x)))$ are divided by $(x+2)(x-3)$ . Explain why your answers hold regardless of the degree of $P$ .
1. Hint 1
  A remainder after division by a quadratic has degree at most one. Its values at the two zeros of the divisor determine it.
2. Hint 2
  Track what happens to $-2$ and $3$ after two and after three applications of $P$ .
Answer

The two remainders are $0$ and $1-x$ , respectively.

Full solution

The given rule sends $-2$ to $3$ and $3$ back to $-2$ .
Consequently $P(P(-2))=-2$ and $P(P(3))=3$ .
Thus the polynomial $P(P(x))-x$ vanishes at both $-2$ and $3$ .
The factor theorem supplies the two distinct factors $x+2$ and $x-3$ , so their product divides this polynomial and its remainder is zero.

After three applications, $-2$ again goes to $3$ , and $3$ goes to $-2$ .
The remainder $R(x)=ax+b$ of $P(P(P(x)))$ must therefore satisfy $R(-2)=3$ and $R(3)=-2$ .
Subtracting gives $5a=-5$ , hence $a=-1$ and $b=1$ .
Conversely, subtracting $1-x$ from the triple composition leaves a polynomial vanishing at both zeros of the divisor, which verifies the remainder directly.
Both arguments use only evaluations and the factor theorem; the size of the composed polynomial never enters the calculation.

Answer

The two remainders are $0$ and $1-x$ , respectively.

Key idea

To find a remainder, evaluate a complicated polynomial where the divisor vanishes instead of expanding it.
Problem 1: Mark complete
Problem 2 The least degree compatible with three reports

Difficulty: 1 of 3 stars, Stretch

A monic real polynomial $P$ leaves remainder $3$ when divided by either $x-1$ or $x+1$ , and leaves remainder $2x+3$ when divided by $x^2+1$ . Determine its least possible degree and find every polynomial of that degree satisfying the reports. Prove that a lower degree is impossible.
1. Hint 1
  Start with $P(x)=2x+3+(x^2+1)Q(x)$ and use the two reported values at $1$ and $-1$ .
2. Hint 2
  You should obtain $Q(1)=-1$ and $Q(-1)=1$ . Hence $Q(x)+x$ has both $1$ and $-1$ as roots.
Answer

The least degree is $4$ , and the unique polynomial of that degree is $P(x)=x^4-x^3+x+2$ .

Full solution

The quadratic remainder report gives $P(x)=2x+3+(x^2+1)Q(x)$ for a real polynomial $Q$ .
Evaluating at $1$ and $-1$ yields $Q(1)=-1$ and $Q(-1)=1$ .
Therefore $Q(x)+x$ is divisible by $x^2-1$ , and $Q(x)=-x+(x^2-1)S(x)$ for a polynomial $S$ .
Substitution gives the complete form
$P(x)=-x^3+x+3+(x^4-1)S(x).$

If $S=0$ , the result has leading coefficient $-1$ , so it is not monic.
If $S\ne0$ , the second term has degree $4+\deg S$ , exceeding the degree of the first term; its leading coefficient is the leading coefficient of $S$ .
Thus a monic result must have degree at least $4$ .
Degree $4$ requires $S$ to be a nonzero constant, and monicity forces that constant to be $1$ .
This gives
$P=x^4-x^3+x+2.$
Its displayed complete form verifies all three remainder reports, so the minimum degree and uniqueness are proved.

Answer

The least degree is $4$ , and the unique polynomial of that degree is $P(x)=x^4-x^3+x+2$ .

Key idea

Expressing all solutions to remainder conditions can reveal a leading-coefficient obstruction that interpolation alone can miss.
Problem 2: Mark complete
Problem 3 Two values rule out rational roots

Difficulty: 1 of 3 stars, Stretch

A monic polynomial $P$ has integer coefficients. Suppose $P(u)=P(v)=1$ for integers $u,v$ with $|u-v|\ge3$ . Prove that $P$ has no rational root. Does this force it to have no real root? Settle that question with an explicit monic quadratic example satisfying the hypothesis.
1. Hint 1
  The Rational Root Theorem says that any rational root of a monic integer polynomial must be an integer.
2. Hint 2
  For integers $r,u$ , the difference $r-u$ divides $P(r)-P(u)$ . If $P(r)=0$ and $P(u)=1$ , how far can $r$ be from $u$ ?
Answer

No rational root is possible. Real roots can exist: $P(x)=x^2-3x+1$ has $P(0)=P(3)=1$ and roots $(3\pm\sqrt5)/2$ .

Full solution

If a rational root $r$ existed, monicity and the Rational Root Theorem would make $r$ an integer.
For any integer-coefficient polynomial, $r-u$ divides $P(r)-P(u)$ : each power difference $r^j-u^j$ contains the factor $r-u$ , and adding the integer-coefficient terms preserves divisibility.
Here $P(r)-P(u)=-1$ , so $r-u=1$ or $r-u=-1$ .
Similarly, $r-v=\pm1$ .
Consequently $|u-v|\le|u-r|+|r-v|=2$ , contradicting the hypothesis.
Neither divisor is zero, since $P(u)=P(v)=1$ differs from $P(r)=0$ .

The argument excludes rational roots only.
The polynomial $x^2-3x+1$ is monic with integer coefficients and takes value $1$ at $0$ and $3$ .
Its discriminant is $5>0$ , so the quadratic formula gives the two real roots $(3\pm\sqrt5)/2$ .
They are irrational, as required by the first part.
Thus a strong arithmetic restriction on roots need not prevent the graph from crossing the real axis.

Answer

No rational root is possible. Real roots can exist: $P(x)=x^2-3x+1$ has $P(0)=P(3)=1$ and roots $(3\pm\sqrt5)/2$ .

Key idea

Polynomial values at separated integers can exclude integer roots through divisibility, while leaving irrational roots untouched.
Problem 3: Mark complete
Problem 4 Which integer root could be hidden?

Difficulty: 2 of 3 stars, Challenge

A polynomial $P$ with integer coefficients satisfies $P(0)=12$ and $P(3)=3$ . Determine exactly which integers can be roots of at least one such polynomial. For each possible integer root, construct a polynomial realizing it. A list of necessary divisibility conditions is not sufficient: show that every survivor really can occur.
1. Hint 1
  If $r$ is an integer root, then $r$ divides $12$ and $r-3$ divides $3$ . Combine these short divisor lists.
2. Hint 2
  If $P(x)=(x-r)Q(x)$ , then $Q$ also has integer coefficients. Test the surviving candidates against the fact that $Q(3)-Q(0)$ must be divisible by $3$ .
Answer

Exactly $r=2$ and $r=4$ can occur. Examples are $P(x)=3(x-2)^2$ and $P(x)=-3(x-4)$ , respectively.

Full solution

An integer root $r$ is neither $0$ nor $3$ , since the reported values there are nonzero.
The difference-divisibility property gives $r\mid12$ and $r-3\mid3$ .
The second condition restricts $r$ to $0,2,4,6$ ; discarding $0$ and checking divisibility of $12$ leaves $2,4,6$ .
These are necessary candidates, but they are not yet a complete answer.

If $r=6$ , divide by the monic factor $x-6$ .
Synthetic division shows the quotient $Q$ has integer coefficients.
The two values force $Q(0)=12/(-6)=-2$ and
$Q(3)=3/(-3)=-1.$
But an integer polynomial always has $Q(3)-Q(0)$ divisible by $3$ , whereas this difference is $1$ .
Thus $6$ is impossible.
For $r=2$ , the polynomial $3(x-2)^2$ has values $12$ and $3$ at the required inputs.
For $r=4$ , the polynomial $-3(x-4)$ has the same values.
Both have integer coefficients and their claimed roots.
The candidate reduction and the two constructions prove exact completeness.

Answer

Exactly $r=2$ and $r=4$ can occur. Examples are $P(x)=3(x-2)^2$ and $P(x)=-3(x-4)$ , respectively.

Key idea

Necessary root divisibility can leave false candidates; applying the same principle to the quotient can detect the missing obstruction.
Problem 4: Mark complete
Problem 5 Exactly how many copies of a factor?

Difficulty: 2 of 3 stars, Challenge

Let $n\ge2$ be an integer. Find the remainder when $x^n$ is divided by $(x-1)^2$ . Then determine the largest integer $k$ for which $(x-1)^k$ divides $x^n-nx+n-1$ . Prove your result without derivatives or the binomial theorem.
1. Hint 1
  Begin with $x^n-1=(x-1)(1+x+\cdots+x^{n-1})$ and subtract $n(x-1)$ .
2. Hint 2
  After taking out one factor $x-1$ , rewrite the remaining expression as a sum of terms $x^j-1$ . Factor each of those once more, and evaluate the final quotient at $x=1$ .
Answer

The remainder is $nx-(n-1)$ , and the largest exponent is $k=2$ .

Full solution

Using the geometric factorization gives $x^n-nx+n-1=(x-1)\bigl((1+x+\cdots+x^{n-1})-n\bigr)=(x-1)\sum_{j=1}^{n-1}(x^j-1)$ .
Each summand is divisible by $x-1$ , so the entire expression equals $(x-1)^2G(x)$ , where
$G(x)=\sum_{j=1}^{n-1}(1+x+\cdots+x^{j-1}).$
This supplies the division identity
$x^n=(x-1)^2G(x)+nx-(n-1).$
The final term has degree at most one, so it is the required remainder.

To decide whether a third copy of $x-1$ is hidden, evaluate the quotient:
$G(1)=1+2+\cdots+(n-1)=n(n-1)/2>0.$
The sum formula follows by pairing the list with its reverse.
By the factor theorem, $x-1$ does not divide $G$ .
Therefore exactly two copies divide the original expression, including at the smallest permitted value $n=2$ , when $G=1$ .
The argument identifies the exact multiplicity through ordinary factorization and a nonzero quotient value.

Answer

The remainder is $nx-(n-1)$ , and the largest exponent is $k=2$ .

Key idea

To prove the exact multiplicity of a factor, extract it explicitly and then evaluate the remaining quotient at the root.
Problem 5: Mark complete
Problem 6 A claim with one missing hypothesis

Difficulty: 2 of 3 stars, Challenge

A student claims: "If a monic real polynomial takes an integer value at every integer input, then every rational root must be an integer."

Disprove the claim with a monic cubic that has a noninteger rational root, and prove that no counterexample of degree $1$ or $2$ is possible. Explain the precise distinction that prevents a direct use of the Rational Root Theorem.
1. Hint 1
  Taking integer values does not necessarily mean having integer coefficients. The product of two consecutive integers is always even.
2. Hint 2
  Try a monic cubic with roots $0,-1,1/2$ . For a monic quadratic, use its values at $0$ and $1$ to constrain the other two coefficients.
Answer

A counterexample is $P(x)=x(x+1)(x-1/2)=x^3+(x^2-x)/2$ , with noninteger root $1/2$ . The minimum possible degree is $3$ .

Full solution

Take
$P(x)=x(x+1)(x-1/2)=x^3+(x^2-x)/2.$
It is monic and has the rational noninteger root $1/2$ .
For every integer $n$ , the product $n(n-1)$ is even, so $P(n)=n^3+n(n-1)/2$ is an integer, including for negative inputs.
Thus it satisfies the claimed hypothesis while contradicting the conclusion.

For a monic linear polynomial $x+c$ , the integer value at $0$ makes $c$ an integer, so its root is integral.
For a monic quadratic $x^2+bx+c$ , the value at $0$ makes $c$ an integer, and the value at $1$ then makes $b=P(1)-1-c$ an integer.
The Rational Root Theorem applies to this quadratic and forces every rational root to be an integer.
These arguments show that degree three is minimal.
The missing hypothesis in the original claim is that the coefficients themselves are integers.
The cubic has two coefficients equal to $\pm1/2$ , even though cancellation makes every integer input produce an integer output.

Answer

A counterexample is $P(x)=x(x+1)(x-1/2)=x^3+(x^2-x)/2$ , with noninteger root $1/2$ . The minimum possible degree is $3$ .

Key idea

Distinguish integer coefficients from integer-valued outputs before applying an arithmetic theorem about polynomial roots.
Problem 6: Mark complete
Problem 7 A remainder after composition

Difficulty: 2 of 3 stars, Challenge

A real polynomial $P$ leaves remainder $2x+1$ when divided by $(x-1)^2$ and remainder $5x-11$ when divided by $(x-3)^2$ . Find the remainder of $P(P(x))$ upon division by $(x-1)^2$ . Explain why the values $P(1)$ and $P(3)$ alone would not determine this remainder.
1. Hint 1
  Write $x=1+u$ , keeping all terms containing $u^2$ together. The first report says $P(x)=3+2u+u^2A(x)$ .
2. Hint 2
  Use the second report with input $P(x)$ : $P(P(x))=5P(x)-11+(P(x)-3)^2B(P(x))$ .
Answer

The required remainder is $10x-6$ . Values alone do not fix the linear part of a remainder at a repeated factor.

Full solution

Write $u=x-1$ .
The first division report gives $P(x)=3+2u+u^2A(x)$ for a polynomial $A$ .
The second gives the identity $P(t)=5t-11+(t-3)^2B(t)$ for a polynomial $B$ .
Substitute $t=P(x)$ .
Because $P(x)-3=u(2+uA(x))$ , its square is divisible by $u^2$ .
Therefore $P(P(x))=4+10u+u^2C(x)$ for a polynomial $C$ .
Replacing $u$ by $x-1$ shows the remainder is
$4+10(x-1)=10x-6.$
The displayed polynomial identities justify discarding the higher powers; no limiting or derivative argument is involved.

The given reports imply $P(1)=3$ and $P(3)=4$ , but those values alone are weaker.
For example, the line $R(x)=(x+5)/2$ has the same two values, yet $R(R(x))=(x+15)/4$ , whose remainder modulo $(x-1)^2$ is itself.
It differs from $10x-6$ .
Thus evaluation at the repeated root determines the constant part in powers of $x-1$ , but does not determine the linear part.
The two full remainder reports supply the additional information needed for composition.

Answer

The required remainder is $10x-6$ . Values alone do not fix the linear part of a remainder at a repeated factor.

Key idea

For repeated factors, keep the first-order remainder as well as the value; polynomial identities allow composition without expansion.
Problem 7: Mark complete
Problem 8 Five small values block every factorization

Difficulty: 3 of 3 stars, Deep challenge

Consider the polynomial $P(x)=(x+5)(x+2)x(x-1)(x-4)+1$ . Prove that $P$ cannot be written as a product of two nonconstant polynomials with integer coefficients. Do not expand the quintic or calculate its roots.
1. Hint 1
  At five distinct integer inputs, $P$ equals $1$ . What integer values could each proposed factor have at those inputs?
2. Hint 2
  In any factorization of a degree-five polynomial, one nonconstant factor has degree at most two. Consider the polynomial formed by squaring that factor and subtracting $1$ .
Answer

No such factorization exists.

Full solution

Suppose $P(x)=A(x)B(x)$ with both factors nonconstant and all their coefficients integers.
Their degrees sum to $5$ , so we may choose the names so that
$1\le\deg A\le2.$
At each of the five inputs $-5,-2,0,1,4$ , the product $A(x)B(x)$ equals $1$ .
Each factor value is an integer, so $A(x)$ must be either $1$ or $-1$ at every one of those inputs.

Thus the polynomial $A(x)^2-1$ has five distinct roots, although its degree is at most $4$ .
A nonzero polynomial of degree at most $4$ cannot have five distinct roots: the factor theorem allows us to remove one linear factor for each distinct root, reducing the degree at each step.
Therefore $A(x)^2-1$ would have to be the zero polynomial.
But for nonconstant $A$ , its square has positive degree and subtracting a constant cannot remove its leading term.
This contradiction rules out every proposed factorization.
The small evaluation values force the obstruction without revealing any root of the quintic itself.

Answer

No such factorization exists.

Key idea

Integer values of $1$ constrain every factor to $\pm1$ ; a root-count bound can turn those constraints into an irreducibility proof.
Problem 8: Mark complete
Problem 9 A polynomial that respects squaring

Difficulty: 3 of 3 stars, Deep challenge

(a) Classify all real polynomials $P$ satisfying $P(x^2)=P(x)^2$ for every real $x$ .

(b) How does the classification change if the condition is instead $P(x^3)=P(x)^3$ for every real $x$ ? Your proof must cover polynomials of every degree, including constant and zero polynomials.
1. Hint 1
  If $P$ is nonzero, factor out its smallest power of $x$ with a nonzero coefficient. Compare the lowest-degree terms on both sides.
2. Hint 2
  After normalizing the remaining constant term to $1$ , suppose its first nonconstant term is $ax^j$ . Compare the first nonconstant terms after substitution and after squaring or cubing.
Answer

(a) $P=0$ or $P(x)=x^k$ for an integer $k\ge0$ . (b) $P=0$ or $P(x)=x^k$ or $P(x)=-x^k$ , with $k\ge0$ .

Full solution

The zero polynomial works in both parts.
For a nonzero polynomial, write $P(x)=cx^kQ(x)$ , where $k\ge0$ , $c\ne0$ , and $Q(0)=1$ .
This factors out the lowest nonzero term.
In part (a), comparing coefficients of $x^{2k}$ gives $c=c^2$ , hence $c=1$ .
Canceling the common power leaves the polynomial identity
$Q(x^2)=Q(x)^2.$
If $Q$ were nonconstant, let $ax^j$ be its nonzero term of smallest positive degree.
Then the first nonconstant term on the left has degree $2j$ , whereas on the right the coefficient of $x^j$ is $2a\ne0$ .
This is impossible.
Thus $Q=1$ and $P=x^k$ .

For part (b), the same lowest-term comparison gives $c=c^3$ , so $c=1$ or $c=-1$ .
Canceling gives
$Q(x^3)=Q(x)^3.$
If its first positive-degree term were $ax^j$ , the left side would have no nonconstant term below degree $3j$ , but the right side would have coefficient $3a\ne0$ at degree $j$ .
Again $Q=1$ .
Conversely, direct substitution verifies every listed monomial, both signs in part (b), and the zero polynomial.
Taking $k=0$ includes all allowed nonzero constants.

Answer

(a) $P=0$ or $P(x)=x^k$ for an integer $k\ge0$ . (b) $P=0$ or $P(x)=x^k$ or $P(x)=-x^k$ , with $k\ge0$ .

Key idea

The first nonzero coefficient can force a polynomial identity more efficiently than solving for every coefficient.
Problem 9: Mark complete
Problem 10 Can an integer orbit have three or more steps?

Difficulty: 3 of 3 stars, Deep challenge

A polynomial $P$ with integer coefficients is applied repeatedly. A cycle of length $m$ means distinct integers $a_0,\ldots,a_{m-1}$ such that $P(a_j)=a_{j+1}$ for $0\le j<m-1$ and $P(a_{m-1})=a_0$ .

(a) Prove that every such cycle has length at most $2$ , and give examples attaining lengths $1$ and $2$ .

(b) If integer coefficients are replaced by the weaker condition that $P$ takes integer values at every integer input, construct a quadratic with a cycle of length $3$ . Explain why part (a) no longer applies.
1. Hint 1
  For any integers $u,v$ , the difference $u-v$ divides $P(u)-P(v)$ . Apply this around the cycle to successive differences.
2. Hint 2
  The absolute values of all adjacent differences must be equal. Look at the largest integer in a cycle: what must its previous and next values be?
Answer

(a) Only lengths $1$ and $2$ are possible; $P(x)=x$ and $P(x)=1-x$ provide examples. (b) $P(x)=1+x-3x(x-1)/2$ has the cycle $0\to1\to2\to0$ and is integer-valued at every integer.

Full solution

For an integer-coefficient polynomial, $u-v$ divides $P(u)-P(v)$ because it divides every power difference $u^j-v^j$ .
Suppose a cycle has length $m\ge2$ , and read its indices cyclically.
Its adjacent differences $d_j=a_{j+1}-a_j$ are nonzero, and the divisibility property gives $d_j\mid d_{j+1}$ .
Thus $|d_j|\le|d_{j+1}|$ all the way around the cycle.
Returning to the starting difference forces all absolute values to be the same positive integer $d$ .

Let $M$ be the largest element in the cycle.
Both its predecessor and successor must be $M-d$ , since they differ from $M$ by distance $d$ and cannot exceed it.
In a cycle with $m\ge3$ , the predecessor and successor are distinct entries, contradicting this equality.
Hence $m\le2$ .
The rule $P(x)=x$ fixes each integer, and $P(x)=1-x$ exchanges $0$ and $1$ , establishing sharpness.

For part (b), take
$P(x)=1+x-3x(x-1)/2.$
The product of consecutive integers is even, so the output is an integer at every integer input.
Direct evaluation gives $P(0)=1$ , $P(1)=2$ , and $P(2)=0$ .
Its coefficients include halves, and the difference-divisibility property fails: $2-0$ does not divide
$P(2)-P(0)=-1.$
Thus the exact step supporting part (a) is absent.

Answer

(a) Only lengths $1$ and $2$ are possible; $P(x)=x$ and $P(x)=1-x$ provide examples. (b) $P(x)=1+x-3x(x-1)/2$ has the cycle $0\to1\to2\to0$ and is integer-valued at every integer.

Key idea

Polynomial divisibility can impose global restrictions on integer dynamics; weakening coefficient assumptions can remove those restrictions completely.
Problem 10: Mark complete