So I have a problem consisting of 3 parts:
- Calculate $\phi(221)$.
- Find the inverse of $17 (\textrm{mod}\ 192)$.
- Solve the equation $x^{17} \equiv 37\ (\textrm{mod}\ 221)$. Tip: use problem 1 and 2.
I have already solved 1 and 2 ($\phi(221) = 192$ and inverse of $17 = 113$). Now I am trying to solve $x$ in problem 3 but I can't figure out exactly how I can use my previous answers to help me solve it. The only thing I have so far is that $x^{\phi(221)} = x^{192} = 1$ using Euler's theorem.
The solution in my math book states:
Raise both sides of the equation to the power of $113$ and then use Eulers theorem: $x \equiv (x^{17})^{113} \equiv 37^{113} (\textrm{mod}\ 221)$.
I dont understand how (or why) the inverse of $17 (\textrm{mod}\ 192)$ (AKA $113$) can be used here when we are dealing with mod 221 and not mod 192. Help? I am not very good at modular arithmetic so please explain it to me in detail.
Generally: One solution of $x^k \equiv a \pmod n,$ where $k$ has an inverse $p=k^{-1} \pmod {\varphi(n)},$ and $a,n$ are coprime, is given by $x\equiv a^p \pmod n$.
Proof: If $k$ has an inverse $p$ then $\gcd(k, \varphi(n))=1 $ and by the extended Euclidian algorithm you have $p,q\in\mathbb{Z}$ with $kp+q\varphi(n)=1$. Now compute
$$x^k \equiv (a^{p})^{k} \equiv a^{pk} \equiv a^{1 - q\varphi(n)} \equiv a\cdot a^{-q\varphi(n)} \equiv a\cdot (a^{\varphi(n)})^{-q} \equiv a\cdot 1^{-q} = a \pmod n$$ where Euler's theorem gives $a^{\varphi(n)}\equiv 1 \pmod n$
In your case $37$ and $221$ are coprime; $17$ is prime and therefore has an inverse $\bmod 192$. Therefore the general situation applies.