Polynomials with Integer Coefficients
Consider a polynomial \( P(x)=a_nx^n+\cdots+a_1x+a_0 \) with integer
coefficients. The difference \( P(x)-P(y) \) can be written in the form
\[ a_n(x^n-y^n)+\cdots+a_2(x^2-y^2)+a_1(x-y),\] in which all summands
are multiples of polynomial \( x-y \). This leads to the simple though
important arithmetic property of polynomials from \( \mathbb{Z}[x] \):
Theorem 3.1
If \( P \) is a polynomial with integer coefficients, then
\( P(a)-P(b) \) is divisible by \( a-b \) for any distinct integers \( a \) and
\( b \).
In particular, all integer roots of \( P \) divide \( P(0) \).
There is a similar statement about rational roots of polynomial
\( P(x)\in\mathbb{Z}[x] \).
Theorem 3.2
If a rational number \( p/q \) (\( p,q\in\mathbb{Z} \), \( q\neq
0 \), nzd\( (p,q)=1 \)) is a root of polynomial \( P(x)=a_nx^n+\cdots+a_0 \) with
integer coefficients, then \( p\mid a_0 \) and \( q\mid a_n \).
We have \[ q^nP\left(\frac pq\right)=a_np^n+a_{n-1}
p^{n-1}q+\cdots+a_0q^n.\] All summands but possibly the first are
multiples of \( q \), and all but possibly the last are multiples of \( p \).
Hence \( q\mid a_np^n \) and \( p\mid a_0q^n \) and the claim follows.
Problem 6
Polynomial \( P(x)\in\mathbb{Z}[x] \) takes values \( \pm1 \) at three
different integer points. Prove that it has no integer zeros.
Suppose to the contrary, that \( a,b,c,d \) are integers with \( P(a) \),
\( P(b),P(c)\in\{-1,1\} \) and \( P(d)=0 \). Then by the previous statement
the integers \( a-d,b-d \) and \( c-d \) all divide 1, a contradiction.
Problem 7
Let \( P(x) \) be a polynomial with
integer coefficients. Prove that if \( P(P(\cdots P(x)\cdots))=x \) for
some integer \( x \) (where \( P \) is iterated \( n \) times), then
\( P(P(x))=x \).
Consider the sequence given by
\( x_0=x \) and \( x_{k+1}=P(x_k) \) for \( k\geq0 \). Assume \( x_k=x_0 \). We know
that \[ d_i=x_{i+1}-x_i\mid P(x_{i+1})-P(x_i)=x_{i+2}-x_{i+1}=
d_{i+1}\] for all \( i \), which together with \( d_k=d_0 \) implies \( |d_0|=
|d_1|=\cdots=|d_k| \).
Suppose that \( d_1=d_0=d\neq0 \). Then \( d_2=d \) (otherwise \( x_3=x_1 \) and
\( x_0 \) will never occur in the sequence again). Similarly, \( d_3=d \) etc,
and hence \( x_k=x_0+kd\neq x_0 \) for all \( k \), a contradiction. It follows
that \( d_1=-d_0 \), so \( x_2=x_0 \).
Note that a polynomial that takes integer values at all integer points
does not necessarily have integer coefficients, as seen on the
polynomial \( \frac{x(x-1)}2 \).
Theorem 3.3
If the value of the polynomial \( P(x) \) is integral for
every integer \( x \), then there exist integers \( c_0,\dots,c_n \) such that
\[ P(x)=c_n\binom xn+c_{n-1}\binom x{n-1}+\cdots+c_0\binom x0.\]
The converse is true, also.
We use induction on \( n \). The case \( n=1 \) is trivial;
Now assume that \( n> 1 \). Polynomial \( Q(x)=P(x+1)-P(x) \) is of degree
\( n-1 \) and takes integer values at all integer points, so by the
inductive hypothesis there exist \( a_0,\dots,a_{n-1}\in\mathbb{Z} \) such
that \[ Q(x)=a_{n-1}\binom x{n-1}+\cdots+a_0\binom x0.\] For every
integer \( x> 0 \) we have \( P(x)=P(0)+Q(0)+Q(1)+\cdots+Q(x-1) \). Using the
identity \( \binom 0k+\binom 1k+\cdots+\binom{x-1}k=\binom x{k+1} \)
for every integer \( k \) we obtain the desired representation of \( P(x) \):
\[ P(x)=a_{n-1}\binom xn+\cdots+a_0\binom x1+P(0).\]
Problem 8
Suppose that a natural number \( m \) and a real polynomial \( R(x)=a_nx^n+
a_{n-1}x^{n-1}+\dots+a_0 \) are such that \( R(x) \) is an integer divisible
by \( m \) whenever \( x \) is an integer. Prove that \( n!a_n \) is divisible by
\( m \).
Apply the previous theorem on polynomial \( \frac1m R(x) \) (with the
same notation). The leading coefficient of this polynomial equals
\( c_n+nc_{n-1}+\cdots+n!c_0 \), and the statement follows immediately.
