# Polynomials

## Nature of polynomial roots [7]

### Integer cubic polynomial

A4, 2021

Suppose $$f(x) = x^3 + ax^2 + bx +c$$ with $$a,b,c$$ being integers. Let $$p,q,r$$ denote the roots of $$f$$, possible complex.
(a) If $$f(1)=2021$$, then $$f(x)=(x-1)(x^2+sx+t) + 2021$$ such that $$s$$ and $$t$$ are integers.
(b) There exists $$f(x)$$ with $$c=2021$$ and $$p=2$$.
(c) There exists $$f(x)$$ with $$r=1/2$$.
(d) $$p^2+q^2+r^2$$ does not depend of $$c$$.

Solution (a) True. Compare the coefficients. $$t-1$$ and $$t-s$$ must be integers.
(b) False. Odd-Even argument.
(c) False. Implies that $$1+2a+4b+8c=0$$ which can't be the case.
(d) True. $$p^2+q^2+r^2=(p+q+r)^2-2(pq+qr+rp)= a^2-2b$$.

### Roots of a quartic polynomial

A5, 2017

Find all the roots of the polynomial: $x^{4}+x^{3}+2 x^{2}+x+1=0$

Solution

We factor the polynomial as follows: $$x^{4}+x^{3}+2 x^{2}+x+1=\left(x^{2}+1\right)\left(x^{2}+x+1\right)$$.

So the roots are $$i,-i,\omega$$ and $$\omega^2$$.

A6, 2011

The equation $$x^{2}+b x+c=0$$ has non-zero real coefficients satisfying $$b^{2}>4 c$$. Moreover, exactly one of $$b$$ and $$c$$ is irrational. Consider the solutions $$p$$ and $$q$$ of this equation.

Which of these statements are correct?

• Both $$\; p\;$$ and $$\; q\;$$ must be rational.
• Both $$\;p\;$$ and $$\;q\;$$ must be irrational.
• One of $$\; p\;$$ and $$\; q\;$$ is rational and the other irrational.
• We cannot conclude anything about rationality of $$\; p\;$$ and $$\; q\;$$ unless we know $$\; b\;$$ and $$\; c\;$$.
Solution

(b) Both $$\;p\;$$ and $$\;q\;$$ must be irrational.
Since the discriminant is positive, both the roots must be real. Since $$c\neq 0$$, the roots must be non-zero. We know that $$p+q=-b$$ and $$pq=c$$. If one root is rational and the other is irrational, then both $$b$$ and $$c$$ must be irrational. If both the roots are rational, then both $$b$$ and $$c$$ must be rational. Hence, both $$p$$ and $$q$$ must be irrational.

### Stationary points

A6, 2021

A real number $$r$$ is called a stationary point if $$f^\prime(r)=0$$ where $$f(x)$$ is a degree $$d$$ polynomial.
(a) If $$d=2022$$, then $$f$$ has at least one stationary point.
(b) If $$f$$ has 2021 distinct real roots, then there are at least 2020 stationary points.
(c) If $$f$$ has 2021 distinct real roots, then there are at most 2020 stationary points.
(d) If $$r$$ is a stationary point and $$f^{\prime\prime}(r)=0$$, then $$(r,f(r))$$ is neither a local minima nor a local maxima.

Solution (a) True. $$f^\prime$$ has odd degree, so there is one real root.
(b) True. If $$r_1 < r_2 \ldots < r_{2021}$$ are the roots, then there is a stationary point between $$r_i$$ and $$r_{i+1}$$.
(c) False. $$f$$ can have any number of stationary points without have a single real root.
(d) False. $$f(x) = x^4$$ is a counterexample.

### Find the possible coefficients given the roots

A7, 2018

Suppose $$x^{3}+a x^{2}+b x+8=0$$ is a cubic equation with integer coefficients. Both $$r$$ and $$-r$$ are the roots of the equation, where $$r>0$$ is a real number. List all possible pairs of values $$(a, b)$$.

Solution

Let the third root be $$s$$. By Vieta's formulas we have
\begin{align} -r+r+s &= -a \\ -rs + rs -r^2 &= b \\ -r^2s &= -8 \end{align} which implies that $$b=-r^2$$ must be negative and $$ab=8$$.

So the possible pairs of values of $$(a, b)$$ are $$\{ (-1,-8), (-2,-4), (-4,-2), (-8,-1) \}$$.

### 0,1-polynomial

A7, 2011

When does the polynomial $$1+x+\cdots+x^{n}$$ have $$x-a$$ as a factor? Here $$n$$ is a positive integer greater than 1000 and $$a$$ is a real number.

• if and only if $$\;a=-1$$.
• if and only if $$\;a=-1\;$$ and $$\;n\;$$ is odd.
• if and only if $$\;a=-1\;$$ and $$\;n\;$$ is even.
• We cannot decide unless $$\;n\;$$ is known.
Solution

(b) We have: $f(x)=\frac{1-x^{n+1}}{1-x} \mbox{ for } x\neq 1$ If $$a$$ is a root of $$f$$, then $$a^{n+1}=1$$. Since $$f(1)=n$$, 1 cannot be a root of $$f$$. So $$a\neq 1$$. The only other possibility is $$a=-1$$ with $$n$$ being odd.

### Parity of a polynomial

A2, 2010

A polynomial $$f(x)$$ has integer coefficients such that $$f(0)$$ and $$f(1)$$ are both odd numbers. Prove that $$f(x) = 0$$ has no integer solutions.

Solution

Suppose $$f(x)=c_{n} x^{n}+c_{n-1} x^{n-1}+\cdots+c_{0}$$ Since $$f(0)$$ and $$f(1)$$ are odd numbers, $$c_0$$ is odd and $\text{Parity of } \sum_{i=1}^n c_i \text{ is even}$ Suppose $$f(x)$$ has an integer root $$r$$. Let us see what happens to the parity of $$f(r)$$. For $$n\geq 1$$, the parity of $$r^n$$ is the same as that of $$r$$. So: \begin{align} \text{Parity of }f(r) &= \text{Parity of }r \times \text{Parity of} \sum_{i=1}^n c_i + \text{Parity of }c_0 \\ \text{Parity of }f(r) &= \text{odd} \end{align} Since $$f(r)$$ is an odd number, $$r$$ cannot be a root of the polynomial.

### Degree constraint on the polynomial

B5, 2011

It is given that the complex number $$i−3$$ is a root of the polynomial $$p(x) = 3x^4+10x^3+Ax^2+Bx−30$$, where $$A$$ and $$B$$ are unknown real numbers. Find the other roots.

Solution

Complex roots come in conjugates, so $$-i-3$$ must also be a root. So $$(x-i+3)(x+i+3) = (x^2+6x+10)$$ must be a factor of $$p(x)$$: $p(x) = (x^2+6x+10)(ax^2+bx+c)$ By comparing the coefficients, $$a=3,b=-8,\text{and }c=-3$$. Hence the polynomial is: $(x^2+6x+10)(3x^2-8x-3)$ $= (x^2+6x+10)(x-3)(3x+1)$ Hence, the other roots are 3 and -1/3.

### Only one real root

B8, 2011

Suppose $$f(x) = x^3 + x^2 + cx + d$$, where $$c$$ and $$d$$ are real numbers. Prove that if $$c>1/3$$, then $$f$$ has exactly one real root.

Requires calculus too.

Solution

Since the function has an odd degree as the highest power, it has at least one real root. The function has exactly one real root since it is monotonic in $$\mathbb{R}$$, as proved below.

Lemma. $$f(x)$$ is a monotonic function in $$\mathbb{R}$$.
Proof. Consider the derivative of $$f$$. $f'(x) = 3x^2+2x+c$ The discriminant of the above quadratic, $$2^2-4\cdot3\cdot c$$, is negative when $$c>1/3$$. Hence, $$f'(x)$$ is always positive in $$\mathbb{R}$$. To see why $$f(x)$$ is a strictly increasing function, consider any two points $$a$$ and $$b$$ in $$\mathbb{R}$$ with $$b > a$$. By mean value theorem, there exists an $$\alpha \in (a,b)$$ such that: \begin{align} f^{\prime}(\alpha) &= \frac{f(b) - f(a)}{b-a} \\ f(b) - f(a) &= f^{\prime}(\alpha) (b-a) > 0 \\\\ & \Rightarrow\; f(b) > f(a) \quad\quad\square \end{align}

### Polynomial with positive coefficients

A5, 2015

Consider the polynomial $$p(x)=\left(x+a_{1}\right)\left(x+a_{2}\right) \cdots\left(x+a_{10}\right)$$ where $$a_{i}$$ is a real number for each $$i=1, \ldots, 10$$. Suppose all the eleven coefficients of $$p(x)$$ are positive. Which of these statements are true?

• (i) The polynomial $$p(x)$$ must have a global minimum.
• (ii) Each $$a_{i}$$ must be positive.
• (iii) All real roots of $$p^{\prime}(x)$$ must be negative.
• (iv) All roots of $$p^{\prime}(x)$$ must be real.

Solution

All of them are true.

(i) Since the degree is even, $$p(x)$$ goes to $$+\infty$$ as $$x \rightarrow \pm \infty .$$ So $$p(x)$$ must have a global minimum somewhere.

(ii) The roots of $$p(x)$$ are $$-a_{i}$$s. Since the coefficients of $$p(x)$$ are positive, no nonnegative number is a root of $$p(x)$$. Thus all the $$a_i$$s are positive.

(iii) and (iv) All 10 roots of $$p(x)$$ are real and negative. There is a root of $$p^{\prime}(x)$$ between consecutive roots of $$p(x)$$ (this is valid even in case of multiple roots). So all 9 roots of $$p^{\prime}(x)$$ are real and negative as well. For negativity, one can also note that all coefficients of $$p^{\prime}(x)$$ are positive and apply the logic in (ii) to $$p^{\prime}(x)$$.

### Find a rational polynomial with a given root

B1, 2012

a) Find a polynomial $$p(x)$$ with $$\sqrt{2}+i$$ as a root and $$p(x)$$ having real coefficients.

b) Find a polynomial $$q(x)$$ with rational coefficients and having the least degree such that $$\sqrt{2}+i$$ is a root.

c) Show that any other polynomial $$f(x)$$ with rational coefficients and $$p(\sqrt{2}+i)=0$$ has $$q(x)$$ as a factor.

Solution

(a) Non-real roots of a polynomial with real coefficients occur in conjugate pairs. \begin{align} \text{Let } p(x) &= (x-(\sqrt{2}+i))(x-(\sqrt{2}-i)) \\ &=x^{2}-2 \sqrt{2} x+3 \end{align} Since all the coefficients are real, the above quadratic is an example.

(b) The above polynomial $$p(x)$$ has one irrational coefficient. We try squaring it as follows:

\begin{align} (x-(\sqrt{2}+i))(x-(\sqrt{2}-i)) & = 0 \\ x^{2}-2 \sqrt{2} x+3 & = 0 \\ x^{2}+3 & = 2 \sqrt{2} x \\ (x^{2}+3)^2 & = 8x^2 \end{align}

So $$q(x) = (x^2+3)^2 - 8x^2$$ is a polynomial with integer coefficients with $$\sqrt{2}+i$$ as one of its roots. We found a polynomial with degree 4. We show that 4 is the least degree for which such a polynomial exists.

Lemma. There is no cubic polynomial $$q(x)$$ with rational coefficients with $$q(\sqrt{2} + i) = 0$$.

Proof. Let $$\sqrt{2}+i$$, $$\sqrt{2}-i$$ and $$r$$ be the roots of such a cubic, if it exists. We have: \begin{align} q(x) & = (x^{2}-2 \sqrt{2} x+3)(x-r) \\ & = x^{3}-(2 \sqrt{2}-r)x^2 + 2\sqrt{2}r x - 3r \end{align} If $$q$$ has only rational coefficients, both $$2\sqrt{2}-r$$ and $$3r$$ must be rational (Contradiction). $$\;\;\square$$

(c) Let $$f(x)$$ be a polynomial with rational coefficients such that $$f(\sqrt{2}+i)=0$$. Divide $$f(x)$$ by $$q(x)$$ using long division to get quotient $$a(x)$$ and remainder $$b(x),$$ both polynomials with rational coefficients. $f(x)=q(x)a(x)+b(x)$ Using $$f(\sqrt{2}+i)=0$$ and $$q(\sqrt{2}+i)=0$$ in the equation gives $$b(\sqrt{2}+i)=0$$. Now if the remainder $$b(x)$$ is a nonzero polynomial, then it would have rational coefficients, degree less than 4 and $$\sqrt{2}+i$$ as a root. But we have proved in part (b) that such a polynomial does not exist. Hence, $$b(x)=0$$ which implies that $$f(x)$$ is a multiple of $$q(x)$$.

### Dependent roots

B5, 2020

A monic polynomial has the following property: If $$r$$ is a root, then $$r^2 -4$$ is also a root. Let us denote this property by $$\tau$$.

(i) Prove that there are exactly six such quadratic polynomials and find them.

Note: The original problem in the CMI paper asked to find two quadratics instead of six. CMI has confirmed that this was a mistake.

Solution

Notation. Let $$f(x):=x^2-4$$. Let $$\alpha_1$$ and $$\alpha_2$$ be the roots of the equation $$f(x)=x$$. The values of the roots are: $\alpha_1 = \left( \frac{1+\sqrt{17}}{2} \right) \;\;\;\alpha_2 = \left( \frac{1-\sqrt{17}}{2} \right)$ Suppose $$p(x)$$ is a quadratic polynomial that has the property $$\tau$$. Let $$r_1$$ and $$r_2$$ be the roots of $$p(x)$$. The constraint on the problem means that $$f(r_1) = r_1\mbox{ or } r_2$$ and $$f(r_2) = r_1\mbox{ or }r_2$$. We can find the candidate polynomials by enumerating all four cases. The polynomials obtained are numbered from (i) to (vi) in the table below.

(ii) Consider the same property for cubic polynomials. Describe the process of finding them, but do not try to find the exact polynomials.

Solution

The procedure is similar to the one followed in part (i). Let the function $$f$$ and $$\alpha$$s be as defined in the previous problem. Let $$g(x)$$ be a cubic polynomial with $$r_1,r_2$$ and $$r_3$$ as its roots.

The constraint on the problem means that:
\begin{align} f(r_1) &= r_1 \mbox{ or } r_2 \mbox{ or } r_3 \\ f(r_2) &= r_1 \mbox{ or } r_2 \mbox{ or } r_3 \\ f(r_3) &= r_1 \mbox{ or } r_2 \mbox{ or } r_3 \end{align}

We can find the candidate polynomials by enumerating all $$3^3=27$$ cases.

### An example of the procedure

Consider the following case: \begin{align} f(r_1) &= r_1 \\ f(r_2) &= r_2 \\ f(r_3) &= r_3 \end{align} We get the following cubic polynomials as candidates for this case: \begin{align} &(x-\alpha_1)^3 \\ &(x-\alpha_2)^3\\ &(x-\alpha_1)^2(x-\alpha_2)\\ &(x-\alpha_1)(x-\alpha_2)^2 \end{align}

#### Problem credits

A similar problem appeared in RMO 2007. pdf

### Repeated roots

A9, 2010

Suppose $$\displaystyle f(x)=\frac{x^{n}}{n!}+\frac{x^{n-1}}{(n-1)!}+\cdots+x+1$$.

Show that $$f(x)=0$$ has no repeated roots.

Requires calculus

Solution

Since zero cannot be a root of $$f(x)$$, we focus only on the non-zero roots. Let us assume, for a contradiction, that $$f$$ has a repeated root $$r\neq 0$$.

Fact. If $$r$$ is a repeated root both $$f(r)$$ and $$f^{\prime}(r)$$ must be zero.

On differentiating $$f(x)$$, we get:
$f^{\prime}(x)=\frac{x^{n-1}}{(n-1) !}+\frac{x^{n-2}}{(n-2) !}+\cdots+x+1$

$f(x)-f^{\prime}(x)=\frac{x^{n}}{n!}$

Therefore, $$r$$ cannot be a repeated root since RHS $$\displaystyle = \frac{r^{n}}{n!} \neq 0$$.

## Polynomial functions [5]

### Polynomial that gives only prime powers

B8, 2012

Let $$f(x)$$ be a polynomial with integer coefficients $$f(n)$$ evaluates to a prime power for every integer $$n$$. A prime power is a number of the form $$p^{k}$$, where $$p$$ is prime and $$k$$ a positive integer. Prove that $$f(x)$$ is a constant.

a) If such a polynomial $$f(x)$$ exists, then there is a polynomial $$g(x)$$ with integer coefficients such that for each nonnegative integer $$n$$, $$g(n)$$ is a perfect power of a fixed prime number.

b) Show that $$g(x)$$ as in part (a) must be a constant polynomial.

c) Show that $$f(x)$$ is a constant polynomial.

Solution

(a) Write $$f(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0} .$$ Then $$a_{0}=f(0)=p^{k}$$ for some prime $$p$$ and integer $$k > 0$$. Define $$g(x)=f(p x) .$$ Then $$g(x)$$ is a polynomial such that for each nonnegative integer $$n, g(n)=f(p n)=$$ a perfect power of a prime number. This prime number has to be $$p,$$ because by evaluating we see that $$g(n)=f(p n)$$ is divisible by $$p$$.

(b) Let $$g(x)=b_{n} x^{n}+b_{n-1} x^{n-1}+\cdots+b_{1} x+b_{0} .$$ Then $$b_{0}=g(0)=p^{k} .$$ Consider: $g\left(m p^{k+1}\right)=(b_{n}\left(m p^{k+1}\right)^{n}+b_{n-1}\left(m p^{k+1}\right)^{n-1}+\cdots+b_{1}\left(m p^{k+1}\right)+p^{k}$ Clearly for each non-negative integer $$m$$, this expression is divisible by $$p^{k},$$ but not by $$p^{k+1}$$ (since it is $$p^{k}$$ modulo $$p^{k+1}$$ ). This forces $$g\left(m p^{k+1}\right)=p^{k}$$ for all $$m,$$ since it must be a perfect power of $$p .$$ Thus the polynomial $$g$$ takes the value $$p^{k}$$ infinitely often, so it must be identically equal to $$p^{k}$$. (Otherwise the polynomial $$g(x)-p^{k}$$ would have infinitely many roots.) To finish the problem, note that since $$g(x)=f(p x)$$ is constant, $$f(x)$$ must be constant by the same logic.

### Sum of squares polynomial

A4, 2013

A polynomial $$f(x)$$ with real coefficients is said to be a sum of squares (SoS) if we can write $$f(x)=p_{1}(x)^{2}+\cdots+p_{k}(x)^{2},$$ where $$p_{1}(x), \ldots, p_{k}(x)$$ are polynomials with real coefficients.
Which statements given below are true?

a) If a polynomial $$f(x)$$ is a SoS, then the coefficient of every odd power of $$x$$ in $$f(x)$$ must be 0.

b) If $$f(x)=x^{2}+p x+q$$ has a non-real root, then $$f(x)$$ is a sum of squares.

c) If $$f(x)=x^{3}+p x^{2}+q x+r$$ has a non-real root, then $$f(x)$$ is a sum of squares.

d) If a polynomial $$f(x) > 0$$ for all real values of $$x,$$ then $$f(x)$$ is a sum of squares.

Aside. This kind of polynomial shows up in a research area called algebraic complexity theory. A few former CMI students and faculty work in this area. For example, take a look at this master's thesis [pdf] by Abhiroop Sanyal, if you're curious.

Solution

False-True-False-True

(a) Counterexample: $$(x+1)^2 = x^2+2x+1$$

(b) Complete the square to get $$f(x)=x^{2}+p x+q=\left(x+\frac{p}{2}\right)^{2}+\left(\frac{4 q-p^{2}}{4}\right)$$. Since the roots are non-real the discriminant is negative, which implies $$4 q-p^{2} > 0$$.

(c) Note that $$f(x) \rightarrow-\infty$$ as $$x \rightarrow-\infty,$$ so in particular $$f(x)$$ takes negative values and hence can never be a sum of squares. This applies to any odd degree polynomial.

(d) Since all roots of $$f$$ are non-real and occur in conjugate pairs, $$f(x)$$ is a product of quadratic polynomials each of which is a sum of squares as shown in part (b).

Further reading. A generalization of part (d) is connected to Hilbert's 17th problem [pdf].

### Polynomials that exponentiate

B4, 2013

Suppose $$f(x)$$ is a function from $$\mathbb{R}$$ to $$\mathbb{R}$$ such that $$f(f(x))=f(x)^{2013}$$.

(a) Show that there are infinitely many such functions.

(b) Exactly four of those functions are polynomials.

Solution

(a) Define $$f(0)=0, f(1)=1$$ and $$f(-1)=-1$$. For every other real number $$x,$$ arbitrarily equate $$f(x)$$ to 0,-1 or 1. Any such function satisfies the given condition.

(b) If $$f$$ is a polynomial, then we make two cases.

(i) If $$f(x)=$$ a constant $$c,$$ then the given condition is equivalent to $$c=c^{2013},$$ which happens precisely for three values of $$c,$$ namely $$c=0,1,-1$$ (since we have $$c\left(c^{2012}-1\right)=0,$$ so $$c=0$$ or $$c^{2012}=1$$ ). Thus there are three constant functions with the given property.

(ii) If $$\mathrm{deg}(f)\geq 1$$, then consider its range set $$A=\{f(x) \mid x \in \mathbb{R}\}$$. Now for all $$a \in A,$$ we have by the given property $$f(a)=a^{2013}$$. So the polynomial $$f(x)-x^{2013}$$ has all elements of $$A$$ as its roots. Since there are infinitely many values in $$A$$ (e.g. applying the intermediate value theorem because $$f$$ is continuous), the polynomial $$f(x)-x^{2013}$$ has infinitely many roots and thus must be the zero polynomial, i.e., $$f(x)=x^{2013}$$ for all real number $$x$$.

### Recursive polynomial

A9, 2018

Consider a sequence of polynomials with real coefficients defined recursively as follows: \begin{align} p_{0}(x)&:=\left(x^{2}+1\right)\left(x^{2}+2\right) \cdots\left(x^{2}+1009\right) \\ p_{k+1}(x)&:=p_{k}(x+1)-p_{k}(x) \end{align} with subsequent polynomials defined by for $$k \geq 0 .$$ Find the least number $$n$$ for which $p_{n}(1)=p_{n}(2)=\cdots=p_{n}(5000)$

Solution

$$n=2018$$. Note that $$\operatorname{deg} p_{0}(x)=2018$$ and $$\operatorname{deg} p_{k}(x)=2018-k$$. Define $$g_{n}(x)=p_{n}(x)-p_{n}(1)$$, hence $$g_{n}(x)$$ has degree $$2018-n$$ and 5000 roots.

### Binomial polynomial

A9, 2020

A polynomial $$p(x)$$ of degree $$7$$ satisfies $$p(n)=2^n$$ for $$n=0$$ to $$7$$. Find $$p(10)$$.
Hint: Notice that the polynomial $$g(x) = 1 + x + \frac{x(x-1)}{2}$$ equals $$2^x$$ for $$x\in\{0,1,2\}$$.

Solution

Let us define the binomial polynomial $$\binom{x}{k}$$ as follows: $\binom{x}{k} := \frac{1}{k!} \times x\times (x-1)\times\cdots(x-(k-1))$ for $$k>0$$ and 1 for $$k=0$$. Now consider the 7-degree polynomial $$g(x)$$ defined as: $g(x) := \binom{x}{0} + \binom{x}{1} +\cdots + \binom{x}{7}$ The value of $$g(x)$$ is same as $$p(x)$$ for $$x=0$$ to $$7$$. Recall that if two $$n$$-degree polynomials agree on $$n+1$$ points they must be identical. So, $$g(x) = p(x)$$. \begin{align} p(10) & = g(10) = \binom{10}{0} + \binom{10}{1} +\cdots + \binom{10}{7} \\ & =\: 2^{10} - \left[ \binom{10}{8} +\binom{10}{9}+ \binom{10}{10} \right] \\ & =\: 2^{10} - \left( 45+10+1\right) \\ & = 968 \end{align}

#### Notes

The next problem (B5, 2014) also involves binomial polynomials.

### Difference equations

B5, 2014

(i) Let $$f(x)=a_{n} x^{n}+\cdots+a_{1} x+a_{0}$$ be a polynomial with real non-zero coefficients. What is the leading term of the polynomial $$\Delta f(x):=f(x)-f(x-1)$$?

(ii) Define polynomials $$p_{n}$$ of degree $$n$$ as follows:
\begin{align} p_{0}(x) & =1 \\ p_{1}(x) &=x \\ p_{2}(x) &=\frac{x(x-1)}{2} \\ p_{3}(x) &=\frac{x(x-1)(x-2)}{3!} \cdots \\ &\vdots \\ p_{n}(x)&=\frac{1}{n!} x(x-1)(x-2) \cdots(x-n+1) \\ \end{align}
Show that for any polynomial $$f$$ of degree $$n,$$ there exist unique real numbers $$b_{0}, b_{1}, \ldots, b_{n}$$ such that $$f(x)=\sum_{i=0}^{n} b_{i} p_{i}(x)$$

(iii) A polynomial $$f(x)$$ is called integer-valued if $$f(n)$$ is an integer for every integer $$n$$. Show that if an integer-valued polynomial is expressed in terms of $$p_n$$s as above, the coefficients $$b_{i}$$s obtained in part (ii) are integers.

Solution

(i) After expanding the powers of $$(x-1),$$ the degree $$n$$ terms of $$f(x)$$ and $$f(x-1)$$ cancel out. The degree $$n-1$$ term from $$f(x)$$ cancels with the leading term of $$a_{n-1}(x-1)^{n-1}$$. The only remaining term of degree $$n-1$$ has to come from $$a_{n}(x-1)^{n}$$. So $$\Delta f(x)=n a_{n} x^{n-1}+\mathrm{lower\; degree\; terms}$$. This is similar to the derivative.

(ii) We use induction on the degree of $$f .$$ If $$f(x)=a_{0}$$ is constant, $$b_{0}=a_{0}$$ works uniquely (base case).
Inductive hypothesis. Assume the result for polynomials of degree strictly less than $$n$$ and let $$f$$ be of degree $$n,$$ so $$a_{n} \neq 0 .$$ We are forced to take $$b_{n}=n ! a_{n}$$ by comparing leading coefficients of $$f(x)$$ and $$\sum_{i=0}^{n} b_{i} p_{i}(x) .$$
Now $$f(x)-b_{n} p_{n}(x)$$ is a polynomial of degree $$d < n$$ and hence by induction equals $$\sum_{i=0}^{d} b_{i} p_{i}(x)$$ for unique $$b_{0}, \ldots, b_{d}$$ Therefore $$f(x)=\sum_{i=0}^{n} b_{i} p_{i}(x),$$ where $$b_{d+1}, \ldots, b_{n-1}$$ are all $$0 .$$ To see uniqueness of $$b_{i}^{\prime} s,$$ let $$\sum_{i=0}^{n} b_{i} p_{i}(x)=\sum_{i=0}^{n} c_{i} p_{i}(x) .$$ Subtract all terms with $$b_{i}=c_{i} .$$ If any terms are remaining, compare the leading coefficients on each side to get a contradiction.

Alternate solution. If we are allowed to use linear algebra, it is a one-line proof. The $$p_i$$s form a basis for polynomial functions, so any polynomial has a unique representation.

(iii) Substitute $$x=0,1,2, \ldots$$ one by one in the equation $$f(x)=\sum_{i=0}^{n} b_{i} p_{i}(x)$$ and solve for $$b_{0}, b_{1}, b_{2}, \ldots$$ successively. $$x=0$$ gives $$b_{0}=f(0) .$$ Using $$x=1$$ and 2 gives $$b_{1}=f(1)-b_{0}$$ $$b_{2}=f(2)-b_{0}-2 b_{1} .$$ In general, for all integers $$t, p_{i}(t)=\left(\begin{array}{c}t \\ i\end{array}\right)$$ is an integer. Further, $$p_{i}(t)=0$$ if $$0 \leq t < i$$ and 1 if $$t=i .$$ So $$b_{t}=f(t)-\sum_{i=0}^{t-1} b_{i}\left(\begin{array}{c}t \\ i\end{array}\right),$$ which is an integer by induction.

#### Problem credits

The previous two problems are based on a topic called method of finite differences. It was introduced by Brook Taylor (of Taylor series fame) in 1715 and further developed by Isaac Newton. The similarity to differentiation is not an accident. Read more about it on Wikipedia.

Brook Taylor (1685-1731)

## Polynomial division [3]

### Guess the polynomial

A7, 2020

$$P(x)=10x^{400}+ax^{399}+bx^{398}+3x+15$$. $$(x^2-1)$$ is a factor of $$P(x)$$.

(i) Find $$a$$ and $$b$$.

(ii) Find the sum of reciprocals of all the roots of $$P(x)$$.

Solution

(i) Since $$(x^2-1)$$ is a factor of $$P(x)$$, we must have $$P(1)=P(-1)=0$$. We get two equations: \begin{align} P(1) = 10 + a + b + 3 + 15 = 0 \\ P(-1) = 10 - a + b - 3 + 15 = 0 \end{align} By solving the above equations we get $$a=-3$$ and $$b=-25$$.

(ii) By Vieta's formulas, only the ultimate and the penultimate coefficients matter. The sum turns out to be $$-1/5$$.

### Find the remainders

A8, 2014

(i) What is the remainder when $$f(x)=7 x^{32}+5 x^{22}+3 x^{12}+x^{2}$$ is divided by $$(x^{2}+1)$$?

(ii) What is the remainder when $$x f(x)$$ is divided by $$(x^{2}+1)$$?

Solution

(i) The function has only even powers. Let us put $$z=x^{2}$$. We want to know the remainder of $$7z^{16}+5z^{11}+3z^{6}+z$$ when divided by $$(z+1)$$. By remainder theorem, $7(-1)^{16}+5(-1)^{11}+3(-1)^{6}+(-1)=4$

So we have $$f(x)=q(x)\left(x^{2}+1\right)+4$$, where $$q(x)$$ is some polynomial.

(ii) $$x f(x)=x q(x)\left(x^{2}+1\right)+4x$$, so the second remainder is $$4x$$.

### Integer-valued polynomials

A8, 2016

A function $$g$$ has the property that $$g(n)=3n+5$$ for each of the 15 integers in the range $$[1,15]$$. Which of the statements are true?

• (i) If $$g(x)$$ is a linear polynomial, then $$g(x)=3 x+5$$
• (ii) $$g$$ cannot be a polynomial of degree 10.
• (iii) $$g$$ cannot be a polynomial of degree 20.
• (iv) If $$g$$ is differentiable, then $$g$$ must be a polynomial.

Solution

True-True-False-False

(i) If $$g(x)$$ is linear, it is uniquely determined by any two values.

(ii) If $$g(x)$$ is a polynomial then it is of the form $$q(x)(x-1)(x-2) \cdots(x-15) + 3x+5$$, where $$q(x)$$ is some polynomial. So $$g(x)$$ cannot be a polynomial of degree 10.

The official solution states this fact without a proof. Why should the polynomial have a $$3x+5$$ term? It is not clear. Where is the consecutive property of integers getting used?

This problem is related to difference equations on integer-valued functions. See this paper and in particular Proposition 1 on page 313.

(iii) $$g(x)$$ can have any degree more than 15. To get 20, pick $$q(x)$$ to be $$x^5$$ in the expression in (ii).

(iv) Pick $$q(x)=\sin x$$, for a counterexample.

### Given the remainders, find the polynomials

B5, 2016

Find a single polynomial $$p(x)$$ that has these two properties:
(i) If $$p(x)$$ is divided by $$x^{100}$$, the remainder is the constant polynomial 1.
(ii) If $$p(x)$$ is divided by $$(x-2)^{3}$$, the remainder is the constant polynomial 2.

Requires calculus.

Solution

Conditions (i) and (ii) imply that for some polynomials $$q(x)$$ and $$r(x)$$, we should be able to express $$p(x)$$ as:

\begin{align} p(x) &= q(x)x^{100} + 1 \\ p(x) &= r(x)(x-2)^{3} + 2 \end{align}

Key observation. If we did not have the plus one terms at the end, we could have simply multiplied the two RHS terms. Taking the derivative makes the 1s go away. So let us look at $$p^\prime{(x)}$$.

\begin{align} p^\prime(x) &= 100q(x)x^{99} + q^\prime(x) x^{100} \\ &= x^{99}\times (100q(x) + q^\prime(x) x^{100}) \end{align}

\begin{align} p^\prime(x) &= 3r(x)(x-2)^{2} + r^\prime(x) (x-2)^{3} \\ &= (x-2)^2 \times ( 3r(x) + r^\prime(x)(x-2) ) \end{align}

So $$p\prime(x)$$ has $$x^{99}$$ and $$(x-2)^{2}$$ as factors. We may assume

$p^\prime(x) = Ax^{99}(x-2)^2$

for some constant $$A$$. The assumption is justified since any polynomial whose derivative is divisible by $$x^{99}(x-2)^{2}$$ will leave constant remainders when divided by either of $$x^{100}$$ and $$(x-2)^{3}$$.

So let us find $$p(x)$$ by integrating $$p^\prime (x)$$:

$p(x)=A\left(\frac{x^{102}}{102}-\frac{4 x^{101}}{101}+\frac{4 x^{100}}{100}\right)+B$

We use properties (i) and (ii) to calculate $$A$$ and $$B$$.

\begin{align} p(0)&=B=1 \\ p(2)&=A\left(\frac{2^{102}}{102}-\frac{4 \times 2^{101}}{101}+\frac{4 \times 2^{100}}{100}\right)+1=2 \end{align}

So $$A=2$$ and $$B=1$$.