1
$\begingroup$

So I have a problem consisting of 3 parts:

  1. Calculate $\phi(221)$.
  2. Find the inverse of $17 (\textrm{mod}\ 192)$.
  3. 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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.