I have to determine the solution number of $x^{100} \equiv a\pmod{77}$ according to the value of $a$.
Inverse chinese remainder theorem:
$$
\begin{cases}
x^{100} \equiv a\pmod{11}, \\
x^{100} \equiv a\pmod{7} \\
\end{cases}
$$
Fermat's little theorem:
$$
\begin{cases}
x^{10} \equiv a\pmod{11}, \\
x^{4} \equiv a\pmod{7} \\
\end{cases}
$$
if $a = 0$, both have one solution, but how do I deduce the other solutions?
Best Answer
Hints:
If $a\not\equiv 0\mod 11$, $x \not\equiv 0$ either, and by Fermat, $x^{10}\equiv 1$.
On the other hand, modulo $7$, it is straightforward to compute the possible values of $x^4$, if you write the nonzero values of $x$ as $\pm1,\pm 2,\pm 3$ and double-square them.