Let $P$ be a polynomial with integer coefficients. Suppose that for $n=1,2,3,\ldots ,1998$ the number $P(n)$ is a three-digit positive integer. Prove that the polynomial $P$ has no integer roots.
Problem
Source: Baltic Way 1998
Tags: algebra, polynomial, modular arithmetic, number theory proposed, number theory
mahanmath
11.01.2011 21:33
Suppose not and assume there is a $n$ such that $P(n)=0$ then if $1 \leq r \leq 1997$ and $n=r$ mod 1997 then $1997 \mid P(r)$ ....
Atlas_ha78
17.09.2013 14:40
mahanmath wrote: Suppose not and assume there is a $n$ such that $P(n)=0$ then if $1 \leq r \leq 1997$ and $n=r$ mod 1997 then $1997 \mid P(r)$ .... Can you explain more?Thanks.
---Fermat---
17.09.2013 14:50
Atlas_ha78 wrote: mahanmath wrote: Suppose not and assume there is a $n$ such that $P(n)=0$ then if $1 \leq r \leq 1997$ and $n=r$ mod 1997 then $1997 \mid P(r)$ .... Can you explain more?Thanks. because $n \equiv r (mod 1997)$ Then, $P(n)\equiv P(r) (mod 1997)$ So, $1997|P(r)$ but $P(r)$ is a three-digit number and 1997 is prime. Contradiction!
mavropnevma
17.09.2013 15:03
mahanmath wrote: Suppose not and assume there is a $n$ such that $P(n)=0$ then if $1 \leq r \leq 1997$ and $n=r$ mod 1997 then $1997 \mid P(r)$ .... I'll go back to the original notations, and slightly change the argument. "Suppose not, and assume there is an integer $r$ such that $P(r)=0$. Then for $1 \leq n \leq 1000$ and $n\equiv r \pmod{1000}$ we have $1000 \mid n-r \mid P(n) - P(r) = P(n)$". But $P(n)$ is a $3$-digit positive integer, thus $P(n)<1000$. It has nothing to do with $1997$ being a prime number, and is extremely weak.