# How to solve this modular equation? $x^{19} \equiv 36 \mod 97$.

How to solve the following? $x^{19} \equiv 36 \mod 97$.

I am having trouble figuring this out. Which technique do I need to use? Chinese Remainder or Fermat's Little Theorem?

• Starting from Mark Bennet's $x(36)^5\equiv 1$, we can multiply by $36^{91}$, and obtain the solution $x\equiv 36^{91}$. If we want to actually calculate, we can use the binary method for exponentiation. It is probably not worthwhile, but alternately we can note that $36^5=6^{10}$, and then $x\equiv 6^{86}$. Aug 7 '14 at 21:40

Note that $x^{96}\equiv 1 \mod 97$ and since $95=5\times 19$, we have $$x^{96}=x(x^{19})^5\equiv x(36)^5\equiv 1$$

This you should be able to solve using elementary means (e.g. by computing an inverse of $36 \mod 97$)

You can finish Mark's answer with simple mental arithmetic:

$\ {\rm mod}\ 97\!:\,\ 36^2\equiv 12(3\cdot 36)\equiv 12\cdot 11\equiv 132\equiv 35$

Therefore $\,\underbrace{36^2\equiv 35\,\Rightarrow\,36^3\equiv -1}\,\Rightarrow\,36^6\equiv 1\,\Rightarrow\,x\equiv 36^{-5}\equiv 36$
because $\,\ x^2 \equiv x\!-\!1\,\Rightarrow\ x^3\equiv x^2\!-x\equiv (x\!-\!1)-x\equiv\, -1$

$\displaystyle{(x,97)=1,}$ since $\displaystyle{x^{19}\equiv 36\mod 97.}$

Therefore

$\displaystyle{x^{96}\equiv 1\mod 97\implies 36^5x\equiv 1\mod 97}$

We can see that $\displaystyle{36^5\equiv 62\mod 97.}$

Now we solve the following:

$$62x\equiv 1\mod 97$$

It is:

$$62x\equiv 98\mod 97\implies 31x\equiv 49\mod 97.$$

So we have to solve this equation:

$$31x-97y=49$$

One solution is : $\displaystyle{(36,11)}$, so it is $\displaystyle{x=97k+36,}$thus $\displaystyle{x\equiv 36\mod 97.}$

• When you say "We can see that $36^5 \equiv 62 \mod 97$ " you mean we need to calculate $36^5$ and divide by $97$ to obtain the remainder or is there simpler way?
– user286485
Feb 8 '18 at 2:12