Exercise 1.4.18* (Integer-valued polynomials, the end!)

Question

Suppose that $f(x)$ is an integer-valued polynomial of degree $n$ and that $g = g.c.d.(f(0),f(1),\ldots,f(n))$. Show that $g \mid f(k)$ for all integers $k$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

\begin{proof} 
Write $f(x) = \sum\limits_{j=0}^n c_j\binom{x}{j}$.
As in Exercise 15,  $(c_0,c_1,\ldots,c_n)$ is solution of the linear system
\begin{align*}
f(0) &= c_0\
f(1) &= c_0 + c_1\
f(2) &= c_0 + 2c_1 + c_2\
\cdots\
f(i) &= c_0 + \binom{i}{1} c_1 +  \cdots + \binom{i}{i-1} c_{i-1} + c_i\
\cdots\
f(n) &= c_0 + \binom{n}{1} c_1 +  \binom{n}{2} c_2\cdots + \binom{n}{n-1} c_{n-1} + c_n.\
\end{align*}
Let $g = f(0) \wedge f(1)\wedge \cdots \wedge f(n)$. Then $g\mid f(i)$ for all $i \in [\![0,n]\!]$.

Note that $g \mid c_0 = f(0)$. Reasoning by induction, assume that $g \mid c_0, g \mid c_1,\ldots, g \mid c_{i-1}$ for some $i,\ 1\leq i \leq n$. Then 
$$g \mid f(i) - \left[ c_0 + \binom{i}{1} c_1 +  \cdots + \binom{i}{i-1} c_{i-1} ight] = c_i.$$
The induction is done, so
$$\forall i \in  [\![0,n]\!],\  g \mid c_i.$$
Therefore,  for any integer $k$, using $\binom{k}{j} \in \Z$ (even if $k = -l<0$: then $\binom{k}{j} = (-1)^j \binom{l-1+ j}{j} \in \Z$),
$$g \mid f(k) = \sum\limits_{j=0}^n c_j\binom{k}{j}.$$
\end{proof}

Exercise 1.4.18* (Integer-valued polynomials, the end!)

Answers

Comments

Exercise 1.4.18* (Integer-valued polynomials, the end!)

Answers

Comments

Add answer