# 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.

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).

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$.

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$.