Trying to find the Multiplicative inverse using Euclid's algorithm

gazzer

Guys. I am trying to work out the answer to the following question and I can only get so far and I am puzzled as to the remainder of it so Im hoping somebody can help me.

I attempted the questions

Using Elclid's Alogrithm find the multiplicative inverse of 22 in Z57

So I have the answer to this question but I wanted to attempt it without peaking so I did the following:

57 = 2 x 22 +13
22 = 1 x 13 +9
13 = 1 x 9 + 4
9 = 2 x 4 +1

Then I started working backwards

1 = 9 - 2 x 4
= 9 -2 x (13 -1 x 9)
= -2 x 13 + 7 x 9

This is the point where I am stumped. I figured you multiply -2 by -1 which gives 2 and then take that away from 9 to give 7.

However looking at the answer to the questions the line in bold above should be

-2 x 13 + 3 x 9

Perhaps my brain is fried from a weekend of studying but I cant figure out where the 3 came from.

Id appreciate any help.

Thanks

dandy28

gazzer wrote: »

Guys. I am trying to work out the answer to the following question and I can only get so far and I am puzzled as to the remainder of it so Im hoping somebody can help me.

I attempted the questions

Using Elclid's Alogrithm find the multiplicative inverse of 22 in Z57

So I have the answer to this question but I wanted to attempt it without peaking so I did the following:

57 = 2 x 22 +13
22 = 1 x 13 +9
13 = 1 x 9 + 4
9 = 2 x 4 +1

Then I started working backwards

1 = 9 - 2 x 4
= 9 -2 x (13 -1 x 9)
= -2 x 13 + 7 x 9

This is the point where I am stumped. I figured you multiply -2 by -1 which gives 2 and then take that away from 9 to give 7.

However looking at the answer to the questions the line in bold above should be

-2 x 13 + 3 x 9

Perhaps my brain is fried from a weekend of studying but I cant figure out where the 3 came from.

Id appreciate any help.

Thanks

you are on the right track. The 3 comes from saying 1 + 21.
This is how l worked it:

57=2x22+13
22=1x13+9
13=1x9+4
9=2x4+1

1x57-2x22=13
1x22-1x13=9
1x13-1x9=4
1x9-2x4=1
Using last equation;
1x9-2x4=1
1x9-2(1x13-1x9)=1
1x9-2x13+2x9=1
-2x13+3x9=1 (3 is 1+2)
-2x13+3(1x22-1x13)=1
-2x13+3x22-3x13=1
3+22-5x13=1
3+22-5(1x57-2x22)=1
3+22-5x57+10x22=1
-5x57 +13x22=1

gazzer

dandy28 Thanks a million. Your explanation makes sense and I can see exactly where the figure came from. Phewwwww.

Thanks again.