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!

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.
