1
$\begingroup$

$81$ isn't a prime so I can't use Fermat's little theorem.

$81=3^{4} \Rightarrow \varphi(81)=54$ but about the $gcd(x,81)$ , I don't know if it's equals to $1$ or not

and euler theorem won't help because $x^{54}\equiv 1 \pmod{81}$ and I need to find $x^{31}$

How do I approach this problem?

$\endgroup$
4
  • $\begingroup$ Hint: 1) Find the modular inverse $m$ of $31$ modulo $54$. 2) Show that $x\mapsto x^{31}$ and $x\mapsto x^m$ are inverse of each other in $\Bbb{Z}_{81}^*$. $\endgroup$ – Jyrki Lahtonen Oct 6 '16 at 15:38
  • $\begingroup$ See also: math.stackexchange.com/questions/1952272/… $\endgroup$ – lab bhattacharjee Oct 6 '16 at 15:44
  • $\begingroup$ Can you explain more. The inverse of $31$ is $7$,so? $\endgroup$ – Asaf Oct 6 '16 at 16:00
  • $\begingroup$ Correct. Why does it then follow that if $x^{31}\equiv a\pmod{81}$ with $\gcd(3,a)=1$ then $a^7\equiv x\pmod{81}$? In other words, did you also do part 2. $\endgroup$ – Jyrki Lahtonen Oct 6 '16 at 19:26
2
$\begingroup$

As $(31,54)=1$ we find by trial $1=31\cdot7-4\cdot54$

$$x^{31\cdot7-4\cdot54}=(x^{31})^7\cdot(x^{54})^{-4}\equiv2^7\cdot1^{4}\pmod{81}$$

$\endgroup$
11
  • $\begingroup$ @JyrkiLahtonen, Are you talking about $7,-4$ then find my answer here : math.stackexchange.com/questions/407478/… $\endgroup$ – lab bhattacharjee Oct 6 '16 at 15:41
  • $\begingroup$ @JyrkiLahtonen, My answer is directed to all my readers as well :) I'm also ready to respond to the questions of my readers. $\endgroup$ – lab bhattacharjee Oct 6 '16 at 15:45
  • $\begingroup$ But you use euler theorem ,how can you make sure that $gcd(x,81)=1$? $\endgroup$ – Asaf Oct 6 '16 at 15:52
  • $\begingroup$ @Asaf, Good Question. If $3$ divides $x,3$ must divide $x^{31}$ and definitely $$3\nmid{x^4-2}$$ But we need $81|(x^{31}-2)\implies3$ must divide $$x^4-2$$ $\endgroup$ – lab bhattacharjee Oct 6 '16 at 15:56
  • $\begingroup$ $\require{cancel}$ If $3\mid x$ so $3^{31} \mid x^{31}$. How and why you conclude that $3 \cancel{\mid} x^{4} - 2$ ? $\endgroup$ – Asaf Oct 6 '16 at 16:16
2
$\begingroup$

This question is screaming for Hensel's Lemma. Let $f(x) = x^{31}-2$. Solve $f(x) \equiv 0 \pmod{3}$ and get $x\equiv 2 \pmod{3}$. Then lift to 9 to get $x\equiv 2 \pmod{9}$. Then lift to 27 to get $x\equiv 20 \pmod{27}.$ And finally lift to 81 to get $x\equiv 47 \pmod{81}$.

$\endgroup$

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.