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