Lowest degree polynomial vanishing on the integers mod $n$? This problem comes from D.J. Newman's A Problem Seminar. 
Problem: What is the lowest degree monic polynomial $p(x)$ such that the value of $p(x)$ is divisible by $100$ whenever $x$ is an integer?
(The number $100$ is not particularly special. You may want to try solving it when $100$ is replaced by an arbitrary integer $n$.)
 A: HINT: 
We have $x^5\equiv x\pmod 5$ and $x^5\equiv x\pmod 2$, therefore 
$$x^{10}-2x^6+x^2=(x^5-x)^2$$
is a multiple of $100$ for all integers $x$.
Remains to show that no degree $\le 9$ works.
Here's how to reduce this to $d\le 5$:
Let $p$ be monic of minimal degree $d$ with $p(x)\equiv0\pmod{100}$ for all $x\in\mathbb Z$.
Wlog. $p(0)=0$.
Then the first difference $\Delta p(x)=p(x+1)-p(x)$ is also a multiple of $100$ for all integers, but is not monic. In fact, it starts with $d\cdot x^{d-1}$ (from $(x+1)^d-x^d=dx^{d-1}+\ldots$). Assume $5<d<10$. As $\gcd(d,25)=1$, find $u,v$ with $ud+25v=1$. Then $u\Delta p + 25vx^{d-1}$ is monic, divisible by $25$ at integers and has degree $d-1$. Modulo $4$, all monomials are congruent at interger arguments to one of $1, x, x^2, x^3$ (because $x^4\equiv x^2\pmod 4$), hence divisibility by $4$ can be achieved by adding a degree $3$ polynomial $q$. Thus $u\Delta p + 25vx^{d-1}+q$ is monic, of degree $d-1$ and a multiple of $100$ at integers - contradiction.
We conclude that $d\ge 10$ (and we are done) or $d\le 5$.
