Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It's known that a polynomial $f\in\mathbb{C}[x]$, whose degree is $n$, possesses integer values at each of the points: $0,1,4,\ldots,n^2$. Prove that this polynomial possesses an integer value at $m^2$ for any $m$.

Thanks in advance!

share|cite|improve this question
In what field of numbers do the coefficients of your polynomial lie? $\mathbb{Z}$? $\mathbb{Q}$? $\mathbb{R}$? – D_S Dec 25 '12 at 17:18
Sorry, I forgot to add this information. They are complex numbers. – Michael Dec 25 '12 at 17:20
I tried to use interpolation ( Lagrange polynomial for example ), but I don't know how to use it correctly in this problem. – Michael Dec 25 '12 at 17:34
Apparently I have the same problem. :) – Hurkyl Dec 25 '12 at 17:36
up vote 7 down vote accepted

The polynomial $g(x) = f(x^2)$ takes integer values at $0,\pm 1,\ldots,\pm n$, so it suffices to show that $g(x-n)$ (which has degree $2n$ and integer values at $0,\ldots,2n$) takes an integer value at $m$ for any $m$. This is easy to see by writing $g(x-n)$ in terms of the basis $\binom{x}{0},\binom{x}{1},\binom{x}{2},\ldots$ for the space of polynomials.

share|cite|improve this answer

The first version of this answer contained a mistake. I've corrected that and made it community wiki in case someone might find it useful.

The following proposition, combined with the beautiful observation of D. Savitt that if we define $g(x)=f(x^2)$, the polynomial $g(x-n)$ is of degree $2n$ and has integer values at $0,1,\ldots,2n$, gives another way to solve the problem.

Proposition. Suppose $g\in\mathbb C[x]$ is a polynomial of degree $n$ and $g(k)$ is an integer for $k=0,1,\ldots,n$. Then $g(k)$ is an integer for all $k\in\mathbb Z$.

Proof. We proceed by induction on $n$. Clearly, the claim holds for $n=0$, since in this case, the polynomial is constant, and thus if has one integer value, it is integer everywhere. For the inductive step, assuming $g$ is of degree $n+1$ and $g(k)$ is integer for $k=0,1,\ldots,n+1$, define a new polynomial $h$ by $h(x) = g(x+1)-g(x)$. Now, the highest degree terms of $g(x+1)$ and $g(x)$ cancel in $h$ and thus $h$ is of degree $n$. Furthermore, by the assumptions on $g$ we have that $h(k)$ is an integer for $k=0,1,\ldots,n$. Therefore by the inductive hypothesis $h(k)$ is integer for $k\in\mathbb Z$. But this means $g(k+1)-g(k)$ is an integer for every $k\in\mathbb Z$. Since $g(0)$ is an integer, it follows that $g(k)$ is an integer for all $k\in\mathbb Z$. $\square$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.