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

• try if $x=43$ fulfilles your equation – Dr. Sonnhard Graubner Feb 4 '18 at 16:45
• @Dr.SonnhardGraubner Why would I come up with this? – user7802048 Feb 4 '18 at 16:50
• i have used my TI calculator, TI-83 – Dr. Sonnhard Graubner Feb 4 '18 at 16:51
• @Dr.SonnhardGraubner I'm not asking because for the actual solution. I want to understand how one might approach problems like this in general (even without using a calculator). – user7802048 Feb 4 '18 at 16:58
• Where does the $x^{37}$ come from? $x^{1477}\equiv x^{1477\bmod96}=x^{22}\mod 97$. – Bernard Feb 4 '18 at 17:16

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

• Neat solution. Thank you! – user7802048 Feb 4 '18 at 17:04
• Is there a quicker way to find the order of $54$ other than trying all the divisors of $96$ in increasing order? – user7802048 Feb 4 '18 at 21:12
• In decreasing order. To find the order of $x$, test $x^{48}$ and $x^{32}$. If neither is $1$, then $x$ is primitive. In our case, $x^{48}=1$ but $x^{32}\ne1$, so that $x$ is a square but not a cube. Now try $x^{24}$, equal to $1$ in our case, it’s a fourth power but not a cube. Done. – Lubin Feb 4 '18 at 22:06

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

$$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=?$$