Find $x$ so $x^{31}\equiv 2 \pmod{81}$
By Emma Payne •
$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$ 42 Answers
$\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$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$
