Compute $3^{100} \pmod {9797}$ using Euler's Theorem

Question

Compute $3^{100} \pmod {9797}$. (Hint: You will want to use both Euler’s Theorem and Chinese Remainder Theorem)

I can get to the step where we can take the prime factorization of $9797$. So $9797 = 97 \cdot 101$. What do we do next? Can someone write out a full example step by step?

Answer 1

You have $3^{96}\equiv1\pmod{97}$, hence $3^{100}\equiv3^4=81$. Mod. $101$, $3^{100}\equiv 1$.

On the other hand, a Bézout's relation between $97$ and $101$ (obtained by the extended Euclidean algorithm) is $$25\cdot97-24\cdot 101=1,$$ whence the solution of the system of congruences: $$\begin{cases}x\equiv 81&\mod{97}\\ x\equiv 1&\mod{101}\end{cases}\iff x\equiv1\cdot 25\cdot97-81\cdot24\cdot 101=-193919\equiv 2021 \pmod{9797}.$$

Answer 2

${\rm mod}\ 101\:\,\ x\equiv 3^{100}\equiv\color{#c00}{\bf 1}\ $ by Fermat; and similarly

${\rm mod}\ 97\!:\,\ x\equiv 3^{100}\equiv 3^4\equiv 81\equiv\color{#c00} {\bf 1}\!+\!101k\equiv 1\!+\!4k\iff k\equiv 80/4\equiv 20$

Therefore $\,x \equiv 1+101(20)\equiv 2021\,\pmod{97\cdot 101}$