Monic polynomial $= 0 \mod p$ for all $x$ For a monic polynomial with integer coefficients (leading coefficient of $1$) $f(x)$ where $f(x) \equiv 0$ mod $p$ for all $x$, where $p$ is a prime number how do I show that the degree of the polynomial must be greater than $p$? Frankly I don't even understand how such a polynomial is possible. If it's always $0$ for all choices of $x$, then shouldn't all coefficients be $0$? But then how is it monic?

Well first of all, we see $f(x)$ is not just the zero polynomial, since it is monic. Now consider an integer $n$, since $f(n)\equiv 0\mod p$ for all $n$, that means that $f([n])\equiv 0\mod p$ where $[n]$ is the equivalence class of $n$ mod $p$. Then if we factor $f(x)$ mod $p$ we see that each of the $p$ equivalence classes is a root of the polynomial, hence 

$$(x-i)|f(x)\quad \text{for all } 0\le i\le p-1$$

i.e. $r(x)=x(x-1)\ldots (x-(p-1))|f(x)$ since each $x-i, x-j$ are coprime for $i\ne j$. Indeed this is easy to see as

$$(j-i)^{-1}\big((x-i)-(x-j)\big)=1$$

is a linear combination which is equal to $1$--here I'm using the Euclidean algorithm to compute the gcd, and since we're in a domain, we know if $a|c, b|c$ and $\gcd(a,b)=1$ then $ab|c$.
Since the degree of the divisor $x(x-1)\ldots (x-(p-1))$ is $p$, the degree of $f$ is at least $p$ since $f(x)=r(x)s(x)$ for some polynomial $s(x)$ and we have that $\deg(r(x)s(x))=\deg r(x)+\deg s(x)$. Finally, since the degree for non-zero polynomials is always $\ge 0$, we see that $\deg f(x) \ge p+0=p$.
As to your question as to how this is possible, consider $f(x)=x^p-x$, then by Fermat's little theorem, $a^{p}\equiv a\mod p$ for all $a\in\Bbb Z$, so this is a non-zero polynomial, which is still $0$ mod $p$ whenever you plug in any integer value for $x$. The difference is that it's just divisible by $p$, i.e. congruent to $0$ mod $p$ for all integer $x$, even if it's not equal to $0$.
