2
$\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 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .