# Number of solutions to congruences

Is there any general form to determine the number of non-congruent solutions to equations of the form $f(x) \equiv b \pmod m$?

I solved a few linear congruence equations ($ax \equiv b \pmod m$) and I know those have only one solution because we're basically finding $a^{-1}$ and all the inverses of $a$ are congruent.

What's the number of solutions for congruences of higher degree polynomials? (quadratic, qube, etc).

Thanks a lot.

## 2 Answers

In general if the degree of the polynomial is $d$, then the maximum number of non-congruent solutions $\!\bmod p$ is $d$, but $d$ solutions are not guaranteed.

• This is only true for prime moduli. $x^2\equiv 1\pmod {\!12}\iff x\equiv \{1,5,7,11\}$. CRT implies $x^2\equiv 1\pmod {12}$ has at most $2\cdot 2=4$ roots, since every combination of residues mod $2,3$ gives a unique residue mod $2\cdot 3$. – user26486 May 3 '15 at 21:55
• You're right, I should have included that, thank you. – mathochist May 3 '15 at 22:01

Theorem: a polynomial of degree $n$ has at most $n$ zeroes $\!\bmod p$.

Proof: $ax\equiv b\pmod {\!p}$ has one solution. Assume that any polynomial of degree $n-1$ has at most $n-1$ roots. Consider an arbitrary polynomial $f$ of degree $n$. If it has no zeroes, we're done. Otherwise (let the root be $a$) we can write $f$ as $f(x)=(x-a)g(x)$, where $g$ is a polynomial of degree $n-1$. $f$ then must have at most $1+(n-1)=n$ zeroes. $\ \ \ \square$

Not true for coprime moduli. E.g., $x^2\equiv 1\pmod {\!12}\iff x\equiv \{1,5,7,11\}$.

CRT implies every polynomial of degree $n$ has at most $n^k$ roots mod $p_1p_2\cdots p_k$, where $p_i$ are distinct primes, since any combination of residues mod $p_i$ gives a unique residue mod $p_1p_2\cdots p_k$ and vice versa, and there are $\underbrace{n\cdot n\cdots n}_{k\text{ }n\text{'s}}=n^k$ such combinations.

• I'm sorry, I'm having trouble understanding your proof for that theorem (also, could you tell me how it's called?). Could you explain a bit your conclusions? On the non-prime moduli: What about mod $p_1p_2...p_k$ for non distinct primes? – YoTengoUnLCD May 3 '15 at 22:11
• @YoTengoUnLCD It doesn't have a specific name. It is a proof by induction. First we prove the base case - every polynomial of degree $1$ has at most $1$ root. Then we assume that every polynomial of degree $n-1$ has at most $n-1$ roots and then prove that any arbitrary polynomial of degree $n$ must have at most $n$ roots too. CRT is Chinese remainder theorem. – user26486 May 3 '15 at 22:16