Remember that you are trying to prove that the congruence $f(x)\equiv 0\pmod{p}$ has at most $n$ solutions. (Added. There must be an assumption that $a_n\not\equiv 0\pmod{p}$ missing, by the way)
The argument is essentially the same one we use to prove that a polynomial of degree $n$ has at most $n$ roots in any field: we do induction on the degree.
If $f$ is of degree $0$, a nonzero constant, then it has no solutions and we are fine.
Assume the result holds for any polynomial of degree less than $n$, and that $f$ has degree $n\gt 0$. If $f$ has no roots, then we are done: $0$ is less than $n$, so $f$ satisfies the conclusion. If $f$ has at least one root $r$, then we can use the Factor Theorem to write $f(x) = (x-r) g(x)$ for some polynomial $g$ of degree $n-1\lt n$. If $s$ is a root of $f$ different from $r$, then $0 = f(s) = (s-r)g(s)$; since $(s-r)\neq 0$, then $g(s)=0$. That is, all other roots of $f$ come from roots of $g$. By the induction hypothesis, $g$ has at most $n-1$ roots. So $f$ has at most $1+n-1 = n$ roots.
This proves that, whether $f$ has at least one root or no roots, it has at most $n$ roots, proving the result.
The argument here is the same. If $f(x)\equiv 0 \pmod{p}$ has no solutions, then you are already done: $0$ is less than $n$. So we can consider the case in which there is at least one solution. It's not that the conclusion will not hold in this latter case (in fact, we will prove it does), it's that the conclusion does not immediately follow: from "at least one solution" we cannot immediately conclude "at most $n$ solutions", whereas from "no solutions" we can immediately conclude "and so at most $n$ (since $0$ is less than $n$)".
Now, we use a lemma:
Lemma. Let $r$ be any integer. Then for any nonnegative integer $t$, $x-r$ divides $x^t - r^t$.
Proof. Simply note that $(x-r)(x^{t-1}+x^{t-2}r+\cdots +xr^{t-2}+r^{t-1}) = x^t-r^t.\quad\Box$
Note well: The fact that $x-r$ divides $x^t-r^t$ does not depend on whether $r$ is a root of $f(x)$ or not: it's a simple algebraic fact. It's always true.
Now, if $f(x)$ does have roots modulo $p$, then it has at least one; call it $r$. If $f(x)\equiv 0\pmod{p}$ has at least one root $r$, then we have $f(r)\equiv 0\pmod{p}$. We have $\begin{align*} f(x) &\equiv f(x) - 0\pmod{p}\\ &\equiv f(x) -f(r)\pmod{p}\\ &\equiv a_nx^n + \cdots + a_0 - (a_nr^n +\cdots + a_0) \pmod{p}\\ &\equiv a_n(x^n - r^n) + a_{n-1}(x^{n-1}-r^{n-1}) + \cdots + a_1(x-r) + (a_0-a_0)\pmod{p} \end{align*}$ Now, by the Lemma, $(x-r)$ divides each of $x^n-r^n$, $x^{n-1}-r^{n-1},\ldots,x-r$. So $x-r$ divides $a_n(x^n-r^n)+a_{n-1}(x^{n-1}-r^{n-1}) + \cdots + a_1(x-r).$ (This argument takes the place of the Factor Theorem in the case above).
The conclusion is that if $f(r)\equiv 0\pmod{n}$, then we can write $f(x) \equiv (x-r)g(x)\pmod{p}$ for some polynomial $g(x)$ with integer coefficients. Now the argument proceeds as in the real case: if $f(s)\equiv 0\pmod{p}$, then $(s-r)g(s)\equiv 0 \pmod{p}$, so $g(s)\equiv 0\pmod{p}$. So any other root of $f$ gives a root of $g$, and since $g$ has at most $n-1$ roots modulo $p$, then $f$ has at most $1+(n-1)=n$ roots modulo $p$.