Solve $x^{5} \equiv 2$ mod $221\ $ [Taking modular $k$'th roots if unique]

We know that $221 = 17*13$. So we can check if the system has roots to both of those equations separately, which it does:

$x^{5} \equiv 2$ mod $13$ has the solution $6 + 13n$ and $x^{5} \equiv 2$ mod $17$ has the solution $15 + 17n$.

I got these numbers from wolfram, I have no idea how to solve this problem WITHOUT a calculator. And even after finding these numbers. How would one obtain a solution modulo $221$? I was thinking the Chinese Remainder Theorem but I am under the assumption that CRT only applies to problems with powers of $x$ which are $1$.

Thanks.

Solution 1:

Below we quickly mentally solve $\,x^{\large 5}\equiv 2\,$ by taking a $5$'th root, i.e. raising both sides to power $\color{#c00}{1/5}$

Suppose $a$ is coprime to $13$ & $17$. By little Fermat $\,a^{\large 12}\equiv 1\pmod{\!13},\, $ $a^{\large 16}\equiv 1\pmod{\!17}\,$ hence $\,a^{\large 48}\equiv 1\,$ mod $13\ \&\ 17,\,$ so also mod $\,13\cdot 17 = 221\,$ by CCRT (or lcm). $ $ Applying this: $\bmod{13\cdot 17}\!:\ x^{\large 5}\equiv 2\,$ $\Rightarrow\,x\,$ is coprime to $13,17\,$ so $\,x^{\large 48}\equiv 1.\,$ Similarly $\,\color{#0a0}{2^{\large 24}}\equiv 1\,$ by $\bmod 17\!:\ (2^{\large 4})^{\large 6}\equiv(-1)^{\large 6}\equiv 1$

By Theorem below: $\,x^{\large\color{}{48}}\equiv 1\equiv 2^{\large 48}\,$ and $\,k'\equiv \color{#c00}{1/5 \equiv 29}\pmod{\!48}\ $ [computed below] implies

$$\ \ \ \ \ x^{\large 5}\equiv 2\iff x\equiv 2^{\large\color{#c00}{1/5}}\equiv 2^{\large\color{#c00}{29}}\equiv \bbox[5px,border:1px solid #c00]{2^{\large 5}}\,\ \ {\rm by}\ \ \color{#0a0}{2^{\large 24}}\equiv 1$$

Theorem $ $ [Compute $k$'th root by raising to power $\frac{1}k\!\pmod{\!f}\,$ if $k$ is coprime to $\color{#d0f}{{\rm period}\ f}$]

Given $\ \color{#d0f}{a^f} \equiv 1\equiv \color{#d0f}{b^f}\pmod{\!n},\ $ and $\ k' \equiv \frac{1}k\equiv k^{-1}\pmod{\!f},\, $ so $\ kk' = 1 + jf,\ $ then

$$ \bbox[5px,border:1px solid #c00]{a^{\large\color{#c00} k} \equiv b \iff a \equiv b^{\large (\color{#c00}{1/k})_f}\equiv b^{\large k'}\!\!\!\pmod{\!n}}\qquad$$

$\begin{align}{\bf Proof}\ \ \bmod n\!:\ \ \ &b \equiv a^{\large k}\,\Rightarrow\, b^{\large k'}\! \equiv a^{\large kk'}\! \equiv a^{\large 1+fj} \equiv a(\color{#d0f}{a^{\large f}})^{\large j} \equiv a\\ &a \equiv b^{\large k'}\!\Rightarrow\, a^{\large k} \equiv b^{\large k'k} \equiv \,b^{\large 1+fj} \equiv \,b(\color{#d0f}{b^{\large f}})^{\large j} \equiv b \end{align}$

Remark $ $ Clearly the proof works in any group using $\,\color{#d0f}{f = |G|}\,$ by Lagrange.

For completeness below we compute $\ 1/5 \pmod{\!48}\ $ using Inverse Reciprocity

$\bmod 48\!:\,\ \dfrac{1}5\equiv \dfrac{1\!+\!48(\color{#c00}3)}5\equiv \dfrac{145}5\equiv 29\ $ by $\bmod 5\!:\ 0\equiv 1\!+\!48\color{#c00}x\equiv 1\!-\!2x\!\iff\! {\overbrace{2x\equiv1\equiv6}^{\large \color{#c00}{x\ \equiv\ 3}}}$

Alternatively we can use CRT and compute the $5$'th roots modulo each prime $13,17\,$ as follows, where the left & rightmost equivalences are by CRT, and the middle one is by the Theorem

$x^{\large 5}\!\equiv 2\pmod{\!\!\!\overbrace{221}^{\large 13\,\cdot\, 17}\!\!} \!\!\rm\iff\!\! \begin{align} x^{\large 5}\!\equiv 2\!\!\!\pmod{\!13}\\ x^{\large 5}\!\equiv 2\!\!\!\pmod{\!17}\end{align}$ $\!\!\iff\!\! \begin{align} x&\equiv\ \ 6\!\!\!\pmod{\!13}\\ x&\equiv 15\!\!\!\pmod{\!17}\end{align} \!\!\iff\! x\equiv 32\pmod{\!\!\!\overbrace{221}^{\large 13\,\cdot\, 17}\!\!}$

The first $\!\iff\!$ is by replacing $\,x^{\large 5}\,$ by $X$ then applying CRT (again we need only the trivial constant-case CCRT or lcm). The fraction computations for $\,1/5\,$ in the Theorem in the middle arrow are quickly computed by Inverse Reciprocity as above (or the Extended Euclidean Algorithm)

$\!\bmod 12\!:\ \dfrac{1}5 \equiv \dfrac{1 + 12\,\cdot\, \color{#c00}2}5\ \equiv\ \color{#0a0}5,\ $ by $\bmod 5\!:\ 1\!+\!12\color{#c00}x \equiv 0 \iff x \equiv \dfrac{-1}{12}\, \equiv\, \dfrac{4}2\, =\, \color{#c00}2$

$\!\bmod 16\!:\ \dfrac{1}5 \equiv \dfrac{1\!+\!16(\color{#c00}{-1})}5\! \equiv\! \color{#f84}{-3},\ $ by $\bmod 5\!:\ 1\!+\!16\color{#c00}x \equiv 0 \iff x \equiv \dfrac{-1}{16} \equiv \dfrac{-1}1 = \color{#c00}{-1}$

Plugging the above values of $\,1/5\,$ into the Theorem we obtain the residues $\,x\equiv 6,15\,\bmod\, 13,17$

Thus $\bmod 13\!:\,\ x^{\large 5}\equiv 2\iff x\equiv 2^{\large\color{#0a0}{\:\! 5}}\equiv 6\,\ $ by the Theorem,

and $\ \ \bmod 17\!:\,\ x^{\large 5}\equiv 2\iff x\equiv 2^{\large \color{#f84}{-3}}\equiv\dfrac{1}8\equiv\dfrac{-16}8\equiv -2\equiv 15 $

Finally by Easy CRT $\,\ x\equiv 15+17\left[\dfrac{6\!-\!15}{17}\bmod{\!13}\right]$ $ \equiv15+17\left[\dfrac{4}{4}\right]\equiv \bbox[5px,border:1px solid #c00]{32}\,\ \pmod{\!13\cdot 17} $

But this ends up being more work than the first direct method.

Remark $ $ See here for methods for the more general (non-coprime) case.