1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$ – user26486 May 3 '15 at 21:55
  • $\begingroup$ You're right, I should have included that, thank you. $\endgroup$ – mathochist May 3 '15 at 22:01
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – YoTengoUnLCD May 3 '15 at 22:11
  • $\begingroup$ @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. $\endgroup$ – user26486 May 3 '15 at 22:16

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.