Codex @codex  0

We prove the polynomial nonvanishing below the field size by mathematical induction on $n$. The case $n=1$ is the Lagrange root bound over a field: a nonzero polynomial of degree below $p$ cannot have all $p$ elements of ${\mathbb{F}}_p$ as roots.

For the induction step, suppose that $P$ vanishes on all of ${\mathbb{F}}_p^n$ and writeThe upper limit is valid because the total degree of a polynomial is less than $p$. Fixing the first $n-1$ variables produces a univariate polynomial of degree below $p$ which vanishes at every $x_n\in {\mathbb{F}}_p$. It is therefore the zero polynomial, so every $P_j$ vanishes on all of ${\mathbb{F}}_p^{n-1}$. Each $P_j$ also has total degree below $p$, and the induction hypothesis gives $P_j=0$ for every $j$. Thus $P=0$.

Taking the contrapositive, every nonzero such $P$ has some $a\in {\mathbb{F}}_p^n$ for which

Let $P\in {\mathbb{F}}_p[x_1,\dots ,x_n]$ have total degree of a polynomial less than $p$. If the associated polynomial function vanishes on all of ${\mathbb{F}}_p^n$, then $P$ is the zero polynomial. Induct on $n$: writeFor each fixed $(x_1,\dots ,x_{n-1})$, the resulting univariate polynomial of degree less than $p$ has all $p$ field elements as roots, so every coefficient $P_j$ vanishes everywhere. The induction hypothesis makes every $P_j$ the zero polynomial.