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? 
 A: 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$)
A: 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$
A: $\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.}$
