How to solve the following? $x^{19} \equiv 36 \mod 97$.
I am having trouble figuring this out. Which technique do I need to use? Chinese Remainder or Fermat's Little Theorem?
[Math] How to solve this modular equation? $x^{19} \equiv 36 \mod 97$.
elementary-number-theorymodular arithmetic
Related Solutions
You can try this by "chunks". Since $\;24=4\cdot6\;$ and clearly $\;4\;$ is the square of $\;2\;$ , we can concentrate on $\;6\;$...and we're in luck since
$$6=256\pmod{125}=6+2\cdot125$$
So that $\;16^2=6\pmod{125}\;$ , and finally
$$(32)^2=2^216^2=4\cdot6=24\pmod{125}$$
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 $\color{#c00}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}\ \ $ by Congruence Laws
Remark $ $ Clearly the proof works in any group using $\,\color{#d0f}{f = |G|}\,$ by Lagrange. Said in map language, the theorem shows that the $k$'th power map $\,x^k$ has inverse $(k$'th root) being $\,x^{k'}\,$ (on $\,\Bbb Z_n^{*})$
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 above values of $\frac{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.
Best Answer
Note that $x^{96}\equiv 1 \mod 97$ and since $95=5\times 19$, we have $$x^{96}=x(x^{19})^5\equiv x(36)^5\equiv 1$$
This you should be able to solve using elementary means (e.g. by computing an inverse of $36 \mod 97$)