Solve congruence with large exponents

Question

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.

Answer 1

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$.

Answer 2

Let us find integers $a,b$ such that $37a+96b=1$

Like Solving a Linear Congruence,

$$37\cdot13-96\cdot5=1$$

$$x^{37}\equiv54\pmod{97}$$

$$x=x^{37\cdot13-96\cdot5}\equiv54^{13}$$

Now by observation $2^{10}\equiv54\pmod{97},2^{11}\equiv11$

$$54^{13}\equiv(2^{10})^{13}\equiv2^{130}\equiv2^{34}\equiv2(11)^3=?$$