how to solve this kind of modular arithmetic problems with exponents?

74 Views Asked by At

What is the method of solving similar problems like given below $$x^7 \equiv 25\pmod{54}$$

1

There are 1 best solutions below

3
On

First solve $x^7\equiv25\bmod27$ as follows.

Note that $x^{18}\equiv1\bmod27$ by Euler's theorem, so

$x^7\equiv-2\bmod27\implies (x^7)^{13}\equiv x^{91}\equiv (x^{18})^5x\equiv x\equiv(-2)^{13}\bmod 27.$

Now $2^5=32\equiv5\bmod27$, so $2^{10}\equiv25\equiv-2\bmod27,$ so $x\equiv(-2)^{13}\equiv2\times8\equiv16\bmod 27.$

To have $x^7\equiv25\bmod 54$, we also need $x\equiv1 \bmod2$. Can you take it from here?