Let $p(x)$ be a polynomial with integer coefficients. Show that if $p(2)=3$ and $p(3)=5$ then $p(n)\ne0$ for all integers $n$. Let $p(x)$ be a polynomial with integer coefficients. Show that if $p(2)=3$ and $p(3)=5$ then $p(n) \neq 0$ for all integers $n$.
I did manage to solve it using the fact that $a-b | p(a)-p(b)$ but I found a more elegant solution online and didn,t quite understand it and I am hoping that someone can help me understand it!
If $p(n)=0$ then $p(n)=0 \pmod 2$ as well. But either $n=2 \pmod 2$ or $n=3 \pmod 2$ and in both cases $p(n) = 1 \pmod 2$. The contradiction.
I understand that any number must either be divisible by $2$ or have a remainder of $1$ after division by $2$ but how did they conclude that this would imply that $p(n) = 1 \pmod 2$ from this?
Thanks in advance!
 A: It is your proof using a more fancy language. It isn't more elegant, it's just a different packaging.
You say that $a-b\mid p(a)-p(b)$, and also that for any $n$ you can make either $n-2$ or $n-3$ even, meaning either $p(n)-p(2)$ or $p(n) - p(3)$ must be even. Thus $p(n)$ cannot possibly be $0$.
The proof you found uses the exact same idea, but instead of saying, for instance, "either $p(n)-p(2)$ or $p(n) - p(3)$ must be even", they say

either $p(n)\equiv p(2)\pmod 2$ or $p(n) \equiv p(3)\pmod 2$

Any other difference between the two proofs is, presumably, a similarily elementary rewriting. (I haven't seen the exact phrasings of the two proofs, so I can't be entirely certain of this, of course.)
A: If $n$ is even, then $p(n)\equiv p(2)\bmod 2$ and likewise for $n$ odd. In both cases, we have $p(n)\equiv 1\bmod 2$, so $p$ is odd at every integer.
A: You can also proceede like this:
Since $p(2)=3$ we can write
$$p(x)= k(x)(x-2)+3$$ and since $p(3)=5$ we can write
$$p(x)= l(x)(x-3)+5$$
where $k(x)$ and $l(x)$ are polynomial with integer coefficents. Now suppose there is $n$ such that $p(n)=0$. If we now plug $x=n$ in both equations we get:
$$k(n)(n-2)=-3$$
$$l(n)(n-3)=-5$$
which means that $n-2$ and $n-3$ are odd. A contradiction.
