Extended Euclid's algorithm - multiplicative inverse

• Nov 11th 2010, 09:40 PM
extatic
Extended Euclid's algorithm - multiplicative inverse
Hi All,

Having trouble with using Extended Euclid's algorithm to find multiplicative inverses.
I dont understand the algorithm and the more i learn about it the more my brain dies haha.

If someone could answer the following with simple instructions, that would be awesome.

Compute the multiplicative inverse of 9 under modulo 31 using the Extended Euclid's algorithm
• Nov 12th 2010, 01:45 AM
emakarov
$\underline{31} = 3\cdot\underline{9}+\underline{4}$
$\underline{9}=2\cdot\underline{4}+\underline{1}$

I underlined the "important" numbers, i.e., the initial numbers and the remainders, and I left out ratios. By expressing important numbers (starting with the final remainder 1) through other important numbers, 1 can eventually be expressed as a linear combination of the original two numbers.

Therefore, $1 = 9-2\cdot 4 = 9-2(31-3\cdot9)=7\cdot9-2\cdot31$.
• Nov 12th 2010, 01:45 AM
tonio
Quote:

Originally Posted by extatic
Hi All,

Having trouble with using Extended Euclid's algorithm to find multiplicative inverses.
I dont understand the algorithm and the more i learn about it the more my brain dies haha.

If someone could answer the following with simple instructions, that would be awesome.

Compute the multiplicative inverse of 9 under modulo 31 using the Extended Euclid's algorithm

$31=9\cdot 3+4$

$9=4\cdot 2+1$

$4=4\cdot 1\Longrightarrow (31,9)=1\Longrightarrow \exists x,y\in\mathbb{Z}\,s.t.\,\,31x+9y=1$ .

We now "read" back the above Euclides' Algorithm in order to find $x,y$ (from one line before the last since the

last one only serves to be sure what the gcd is):

$1=9+(-2)\cdot 4=9+(-2)\cdot (31+(-3)\cdot 9)=7\cdot 9+(-2)\cdot 31$ , and from here we get at once that

$9\cdot 7=1+31\cdot 2\Longrightarrow 7=9^{-1}\!\!\pmod{31}$

Tonio