Solve congruence with large exponents I'm trying to solve: > $$ x^{1477} \equiv 54 \mod 97 $$ Applying Euler-Fermat gives: $$ x^{1477} = x^{15\cdot 96 + 37} = x^{37}\cdot x^{{96}^{15}} \equiv x^{37}\cdot 1^{15} = x^{37} \mod 97 $$ So instead of solving $ x^{1477} \equiv 54 \mod 97 $ one can solve $ x^{37} \equiv 54 \mod 97 $. How could I proceed from here? I know about the Chinese Remainer Theorem and Euler-Fermat.

If $x^{37} \equiv 54 \pmod {97}$ then $x^{37\cdot 24} \equiv 54^{24} \equiv 1 \pmod {97}$ because the order of $54 \pmod {97}$ is $24$.

This means the order of $x$ is a common divisor of $96$ and $37 \cdot 24$.

Therefore the order of $x$ is a divisor of $24$, and so $x^{24} \equiv 1 \pmod {97}$.

But if $k$ is a divisor of $24$ then $x^k \equiv 1 \pmod {97}$ implies $1 \equiv x^{37k} \equiv 54^k \pmod {97}$ so $24$ divides $k$.

Therefore the order of $x$ is $24$.

That means $x^{12} \equiv -1 \pmod {97}$.

So $54 \equiv x^{37} \equiv x^{1 + 3\cdot 12} \equiv x\left(x^{12}\right)^3\equiv x(-1)^3 \equiv -x \pmod {97}$

Finally, we obtain $x \equiv -54 \pmod {97}$, or $x \equiv 43$.