[proofplan]
We express the number of zeros $N(f)$ as a sum over $\mathbb{F}_q^n$ of the indicator polynomial $1 - f(x)^{q-1}$, then show this sum vanishes modulo $p$. The key observation is that $\sum_{x \in \mathbb{F}_q^n} 1 = q^n \equiv 0 \pmod{p}$, so $N(f) \equiv -\sum_{x \in \mathbb{F}_q^n} f(x)^{q-1} \pmod{p}$. Expanding $f(x)^{q-1}$ in monomials, each monomial has total degree at most $(q-1)\deg f < n(q-1)$, so some variable $X_j$ appears with exponent $k_j < q - 1$. The sum $\sum_{x_j \in \mathbb{F}_q} x_j^{k_j}$ vanishes for $0 \leq k_j < q - 1$, so by Fubini (summing variable-by-variable) every monomial contributes zero, giving $N(f) \equiv 0 \pmod{p}$.
[/proofplan]
[step:Express $N(f)$ using the indicator identity]
By Fermat's little theorem in $\mathbb{F}_q$, for any $a \in \mathbb{F}_q$ we have $a^{q-1} = 1$ when $a \neq 0$ and $0^{q-1} = 0$. Therefore $1 - f(x)^{q-1}$ equals $1$ when $f(x) = 0$ and $0$ when $f(x) \neq 0$. Summing over all $x \in \mathbb{F}_q^n$:
\begin{align*}
N(f) = \sum_{x \in \mathbb{F}_q^n} \bigl(1 - f(x)^{q-1}\bigr) = q^n - \sum_{x \in \mathbb{F}_q^n} f(x)^{q-1}.
\end{align*}
Since $q = p^k$ for some $k \geq 1$, we have $q^n \equiv 0 \pmod{p}$, so
\begin{align*}
N(f) \equiv -\sum_{x \in \mathbb{F}_q^n} f(x)^{q-1} \pmod{p}.
\end{align*}
[guided]
The indicator identity $1 - a^{q-1}$ converts the counting problem into a polynomial summation. The number of zeros of $f$ equals the sum of the indicator function $\mathbf{1}_{f(x)=0}$ over $\mathbb{F}_q^n$, and this indicator function is itself a polynomial in $x$ (namely $1 - f(x)^{q-1}$). Separating the constant and polynomial parts: the sum of $1$ over $\mathbb{F}_q^n$ is $q^n$, which vanishes modulo $p$ because $q$ is a power of $p$. So modulo $p$, the zero count reduces to $-\sum f(x)^{q-1}$, a purely polynomial sum that we can analyze monomial by monomial.
[/guided]
[/step]
[step:Show every monomial of $f(x)^{q-1}$ sums to zero over $\mathbb{F}_q^n$]
Expand $f(x)^{q-1}$ as a linear combination of monomials $X_1^{k_1} \cdots X_n^{k_n}$. Each such monomial has total degree $k_1 + \cdots + k_n \leq (q-1) \deg f$. By hypothesis $\deg f < n$, so
\begin{align*}
k_1 + \cdots + k_n \leq (q-1) \deg f < n(q-1).
\end{align*}
Since $k_1 + \cdots + k_n < n(q-1)$, the average exponent is strictly less than $q - 1$, so there exists an index $j \in \{1, \ldots, n\}$ with $k_j < q - 1$, i.e., $0 \leq k_j \leq q - 2$.
[claim:Power sums over $\mathbb{F}_q$ vanish for small exponents]
For any integer $0 \leq k \leq q - 2$, we have $\sum_{t \in \mathbb{F}_q} t^k = 0$ in $\mathbb{F}_q$.
[/claim]
[proof]
If $k = 0$, the sum equals $|\mathbb{F}_q| = q \equiv 0$ in $\mathbb{F}_q$ (since $\operatorname{char}(\mathbb{F}_q) = p$ divides $q$).
If $1 \leq k \leq q - 2$, the multiplicative group $\mathbb{F}_q^\times$ is cyclic of order $q - 1$. Let $g$ be a generator of $\mathbb{F}_q^\times$. Since $k < q - 1$, the element $g^k \neq 1$, so $g^k - 1 \neq 0$ in $\mathbb{F}_q$. The map $t \mapsto gt$ is a bijection on $\mathbb{F}_q^\times$, so
\begin{align*}
\sum_{t \in \mathbb{F}_q^\times} t^k = \sum_{t \in \mathbb{F}_q^\times} (gt)^k = g^k \sum_{t \in \mathbb{F}_q^\times} t^k.
\end{align*}
Rearranging: $(1 - g^k) \sum_{t \in \mathbb{F}_q^\times} t^k = 0$. Since $g^k \neq 1$, the factor $1 - g^k \neq 0$, so $\sum_{t \in \mathbb{F}_q^\times} t^k = 0$. Adding the $t = 0$ term (which is $0^k = 0$ for $k \geq 1$) gives $\sum_{t \in \mathbb{F}_q} t^k = 0$.
[/proof]
For any monomial $X_1^{k_1} \cdots X_n^{k_n}$ appearing in $f(x)^{q-1}$, we sum over $\mathbb{F}_q^n$ by factoring the sum variable-by-variable:
\begin{align*}
\sum_{x \in \mathbb{F}_q^n} x_1^{k_1} \cdots x_n^{k_n} = \prod_{i=1}^n \Bigl(\sum_{x_i \in \mathbb{F}_q} x_i^{k_i}\Bigr).
\end{align*}
Since some index $j$ satisfies $0 \leq k_j \leq q - 2$, the factor $\sum_{x_j \in \mathbb{F}_q} x_j^{k_j} = 0$ by the claim, so the entire product vanishes. This holds for every monomial in the expansion, so
\begin{align*}
\sum_{x \in \mathbb{F}_q^n} f(x)^{q-1} = 0 \quad \text{in } \mathbb{F}_q.
\end{align*}
[guided]
The factoring step $\sum_{x \in \mathbb{F}_q^n} x_1^{k_1} \cdots x_n^{k_n} = \prod_{i=1}^n \sum_{x_i \in \mathbb{F}_q} x_i^{k_i}$ works because the summation domain $\mathbb{F}_q^n = \mathbb{F}_q \times \cdots \times \mathbb{F}_q$ is a Cartesian product, and each variable $x_i$ appears in exactly one factor $x_i^{k_i}$ of the monomial. This is the discrete analogue of Fubini's theorem: a product of functions summed over a product set equals the product of the individual sums.
The degree condition $\deg f < n$ is consumed here: it forces every monomial $X_1^{k_1} \cdots X_n^{k_n}$ in $f^{q-1}$ to have total degree less than $n(q-1)$, so some exponent $k_j$ must fall below $q - 1$. If we only knew $\deg f \leq n$, some monomials could have $k_i = q - 1$ for all $i$, and the power sum $\sum_{t \in \mathbb{F}_q} t^{q-1} = q - 1 \neq 0$ would give a nonzero contribution.
[/guided]
[/step]
[step:Conclude that $p$ divides $N(f)$]
Combining the two steps:
\begin{align*}
N(f) \equiv -\sum_{x \in \mathbb{F}_q^n} f(x)^{q-1} \equiv 0 \pmod{p}.
\end{align*}
Therefore $p \mid N(f)$.
[/step]
