Determine the number of solutions of $x^{100} \equiv a\pmod{77}$

Question

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?

Answer 1

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.