1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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}$. $\endgroup$ – André Nicolas Aug 7 '14 at 21:40
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – user286485 Feb 8 '18 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.