Solve $x^3 = 27\pmod {41}$ I don't know how to approach this problem. Can anyone give me a hint? If it matters, the first part of the question was to find the order of $5$ in the field $\mathbb Z_{41}$ (the field mod $41$), which I did, but I'm not sure how it relates to the second part.
Thanks for your help.
 A: The obvious solution is $3$.
Can there be multiple cube roots of the same number in a field? That can only happen if there is a non-trivial cube root of $1$ in the field (why?)
But there is no element of order $3$ in $\mathbb Z_{41}$ (why?)
A: Hint $\ {\rm mod}\ 41\!:\  x^{\large\color{#c00}3}\equiv 3^{\large\color{#c00}3}\!\!\iff\! x\equiv 3\ $ by raising to $\rm\color{#c00}{power\ \ 27\equiv 1/3}  \pmod{\!40},\,$ via $\,\rm\color{#0a0}{\mu Fermat}.$
i.e. $\ \ 3\cdot 27 = 1 + 2\cdot 40\,\Rightarrow\, \color{#c00}{(a^{\large 3})^{\large 27}}\!\equiv a^{\large 1+2\cdot 40}\equiv a(\color{#0a0}{a^{40}})^2\equiv a(\color{#0a0}1)^2\equiv \color{#c00}a,\ $ by $\,\color{#0a0}{a^{40}\equiv 1\ \ \ {\rm for}\ \ a\not\equiv 0}$
Said much more simply:  $\ \ \color{#c00}{(a^{\large 3})^{\large 1/3} \equiv\, a},\, $ by $1/3$ exists mod $\, 40,\,$ by $\gcd(3,40)=1\,$ and Bezout.
Remark $\ $ The proof needs only: $\,3$ is invertible mod $40 =\phi(41),\,$ i.e. we don't need to know the specific value of $\,1/3$ $(\equiv 27).$ But knowing this value is very handy since it allows us to quickly compute cube roots: $ $  powering to $\ 1/3 \equiv 27\pmod{40}\ $ shows, like above, that
$$ {\rm mod}\ 41\!:\,\   x^3\!\equiv a \iff\! x\equiv a^{27},\ \  {\rm i.e.}\,\ \ \color{#c00}{a^{1/3}\equiv a^{27}}$$
Thus we have reduced cube-root computation to the simpler problem of computing powers, which can done quickly by repeated squaring.
The same holds for $\,n$'th powers mod $m$ when $n$ is coprime to $m$, since then $\,1/n = n^{-1}$ exists by Bezout. $ $ This shows that the map $\,x\mapsto x^n$ has  inverse $\,x\mapsto x^k,$ where $\,k\equiv 1/n\pmod{\phi(m)},\,$ when the map is restricted to elements $a$ coprime to $m$.  The innate algebraic structure at the heart of the matter will become clearer when one studies group theory (in particular cyclic groups).
A: Since $\phi(41)=40$, $x^{40}\equiv1\pmod{41}$. This means that $x^{81}\equiv x\pmod{41}$. Therefore,
$$
\left(x^3\right)^{27}\equiv x\pmod{41}
$$
This means that if we know $x^3$ mod $41$, we know $x$ mod $41$. Since $3^3=27$, $x=3$ can be the only one.
A: We shall use the lemma that if $a^r\equiv a^s\pmod{n}$, then $r\equiv s\pmod{\operatorname{ord}_n(a)}$. Note that $6$ is a primitive root $\pmod{41}$, and that $6^5\equiv 27\pmod{41}$. We can write $x^3 = 6^{3k}$ for some $k$, so that $$6^{3k}\equiv 6^5\pmod{41}\implies 3k\equiv 5\pmod{\varphi(41)=40}.$$ It is straightforward to proceed from here.
