# Find $x$ so $x^{31}\equiv 2 \pmod{81}$

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

• 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}^*$. – Jyrki Lahtonen Oct 6 '16 at 15:38
• – lab bhattacharjee Oct 6 '16 at 15:44
• Can you explain more. The inverse of $31$ is $7$,so? – Asaf Oct 6 '16 at 16:00
• 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. – Jyrki Lahtonen Oct 6 '16 at 19:26

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}$$
• @JyrkiLahtonen, Are you talking about $7,-4$ then find my answer here : math.stackexchange.com/questions/407478/… – lab bhattacharjee Oct 6 '16 at 15:41
• But you use euler theorem ,how can you make sure that $gcd(x,81)=1$? – Asaf Oct 6 '16 at 15:52
• @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$$ – lab bhattacharjee Oct 6 '16 at 15:56
• $\require{cancel}$ If $3\mid x$ so $3^{31} \mid x^{31}$. How and why you conclude that $3 \cancel{\mid} x^{4} - 2$ ? – Asaf Oct 6 '16 at 16:16
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}$.