3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.