The congruence $x^2 - 16x +2 \equiv 0\pmod{37}$ has only two solutions? I want to prove that the congruence $x^2 - 16x + 2\equiv 0\pmod{37}$ has only two solutions: $x\equiv 3$ and $x\equiv 13$.  I am assuming this is true because the modulus is prime. Is it true that there are at most $2$ solutions because this is a degree $2$ polynomial?
I see that we can rewrite the congruence as $x^2 - 16x + 39\equiv 0\pmod{37}$ and then factor the LHS into $(x - 13)(x - 3)$.
This is a homework problem so I would most appreciate some suggestion to a proof or some general comments about solving polynomial congruences.
 A: By the factor theorem your quadratic $\equiv (x-3)(x-13).\,$ If it had another root $\,x\equiv a\,$ then $\,(a-3)(a-13)\equiv 0,\,$ so $\,p\mid (a-3)(a-13),\,$ so, by primality $\,p\mid a-3,\,$ or $\,p\mid a-13.\,$ Hence $\,a\equiv 3,\,$ or $\,a\equiv 13.\,$ So there can be no other roots.
Remark $\ $ More generally, $\,\Bbb Z/p = $ integers mod $p$ form a field, and a nonzero polynomial over a field has no more roots than its degree (same for any integral domain).
A: Hint: Complete the square. We get $(x-8)^2-64+2$, so we want to solve the congruence $(x-8)^2\equiv 62\pmod{37}$. We can replace $62$ by $25$. 
And yes, if $P(x)$ is a polynomial of degree $n$  whose lead coefficient is not divisible by the prime $p$, then the congruence $P(x)\equiv 0\pmod{p}$ has at most $n$ solutions. In fact, if $F$ is any field, and $P(x)$ is a polynomial of degree $n$ with coefficients in $F$ and is not the zero polynomial, then the equation $P(x)=0$ has at most $n$ solutions in $F$. 
A: Lagrange's theorem states that if $p$ is prime then a polynomial $f$ of degree $n$ has at most $n$ solutions modulo $p$. 
We can prove this by induction in exactly the same way we would for showing this over $\mathbb C$.  It is certainly true for $n=1$. The inductive step uses the fact that $\mathbb Z/p\mathbb Z$ is a field, and hence an integral domain - i.e. if $xy\equiv 0\pmod p$, then $x\equiv 0\pmod p$ or $y\equiv 0\pmod p$, or put in other terms, $p\mid xy\implies p\mid x\ $ or $p\mid y$. Can you finish the proof?
Note that this is NOT true if $p$ is not prime. For example, $x^2-1$ has $4$ solutions modulo $8$. 
