Modulo Inverse using extended euclidean

Question

My aim here to learn the Chinese Remainder theorem. But am stuck at finding the inverses.

Suppose we have 42 mod 5, but according to the CRT question, we must make it 42 * x congruent to 1 (mod 5)

I know the answer is 3 by hit and trial, but can someone help me solve it using the eulidean and extended eulid alg?

Answer 1

The CRT is not needed to find an inverse modulo a prime: it is just not what it is used for.

Here, we can do as follows:

$$42\pmod5=2\pmod5\implies 42^{-1}\pmod5=2^{-1}\pmod 5=3\pmod 5$$

Why the last equality? Because

$$\;2\cdot 3=1\pmod 5\implies 2=3^{-1}\pmod 5\;\;or\;\;3=2^{-1}\pmod 5\;$$

Answer 2

42 mod 5 is 2, so when you try to invert 42 it's the same as to invert 2 which is easier problem. Basicly, you work only with remainders: 2*0 = 0, 2*1 = 1, 2*2 = 4, 2*3 = 1, 2*4 = 3, and that's all your cases, so clearly 3 inverses 2 and so 42.

More generally, if you want to find $a^{-1}$ $mod$ $m$, you have to solve $ax+my=1$ and if solution exists, then $x$ is your inverse. Clearly it exists when $a$ and $m$ are coprimes. So, as you said, you apply extended Euclidean algorithm on $a$ and $m$ and get coefficients of Bézout's identity $x$ and $y$.

Answer 3

First, note that $42\equiv 2 (\bmod 5)$.

Extended Euclidean Algorithm (one of approaches):

When two numbers $a, m$ are given, $a<m$, $GCD(a,m)=1$, and we need to find $b$, such that $$ a\cdot b = 1 (\bmod~m),\tag{1} $$ then denote $$ r_0 = m, \qquad v_0 = 0; $$ $$ r_1 = a, \qquad\; v_1 = 1; $$ and let's find next values: $$ s_n = \left\lfloor \dfrac{r_{n-1}}{r_n} \right\rfloor; $$ $$ r_{n+1} = r_{n-1}-r_n s_n; $$ $$ v_{n+1} = v_{n-1}-v_n s_n; $$ and repeat it until $r_n=1$ $(r_{n+1}=0)$.

Last value $v_n$ (when $r_n=1$) will figure as solution of equation $(1)$.

It is comfortable to build appropriate table:

Example:

$m=1234$, $a=67$, $b=?$

$$ \begin{array}{|c|r|r|r|ll|} \hline \\ n) & r_n & v_n & s_n & \color{gray}{\mbox{check:} ~~ a \cdot v_n} & \color{gray}{\equiv r_n (\bmod~m)}\\ \hline \\ 0) & r_0=m=\color{red}{1234} & \color{red}{0} & - & & \\ 1) & r_1=a=\color{red}{67} & \color{red}{1} & 18 & \color{gray}{67\cdot 1} & \color{gray}{\equiv 67 (\bmod~1234)} \\ 2) & 28 & -18 & 2 & \color{gray}{67\cdot (-18)} & \color{gray}{\equiv 28 (\bmod~1234)} \\ 3) & 11 & 37 & 2 & \color{gray}{67\cdot 37} & \color{gray}{\equiv 11 (\bmod~1234)} \\ 4) & 6 & -92 & 1 & \color{gray}{67\cdot (-92)} & \color{gray}{\equiv 6 (\bmod~1234)} \\ 5) & 5 & 129 & 1 & \color{gray}{67\cdot 129} & \color{gray}{\equiv 5 (\bmod~1234)} \\ 6) & 1 & -221 & 5 & \color{gray}{67\cdot (-221)} & \color{gray}{\equiv 1 (\bmod~1234)} \\ \color{gray}{7)} & \color{gray}{0} & & & & \\\hline \end{array} $$

So, $b\equiv -221 \equiv 1013 (\bmod~1234)$.