euclids algorithm confuses me somewhat!!!!?

Question

in my last assignment (which has been given to my tutor now!!!) the question was:
13 in Z37
i can manage to do the first 2 stages taking me to
1=11-5x2
= 11-5(13-1x11)
i then get stuck here as i can not work out where to go next or what to do.
this question is really bugging me as i know that it is a simple formula.
can anyone help? (exam in 4 weeks!!!!!!)

find the multiplication inverse of 13 in Z_37?

Answer 1

I think you mean find the inverse of 13 in Z_37 as 13 in Z_37 is just 13.

First let's use Euclid's Algorithm

37 = 2(13) + 11
13 = 1 (11) + 2
11 = 5(2) + 1

Now, here's the part you're probably confused with, which is called Euclid's Extended Algorithm or the Extended Euclid's Algorithm.

Start with 1 like you did:

1 = 1(11) - 5(2)

Now we want to convert these numbers (the ones in parenthesis in the line above this paragraph) using the remainder portions of the lines from the EA so we look for a place where we see 2 and an 11 on the end of a line.

We find that

2 = 1(13) - 1(11)
11 = 1(37) - 2(13).

So now let's plug these into the parenthetical numbers we have from our starting point (I put some extra 1's and parenthesis because I like to think of th enumbers in the parenthesis kind of like variables, even though they're not, that you work with, and the numbers on the outside kind of like "coefficients").

1 = 1(11) - 5(2)
<=>
1 = 1( 1(37) - 2(13) ) - 5( 1(13) - 1(11) )

Now it might be tempting to cut some corners or simplify everything in the end, but I recommend a "clean-up" between each step before we go on, so distributing the numbers and keeping the single numbers within parentheses intact (but collecting them), we have

1 = 1( 1(37) - 2(13) ) - 5( 1(13) - 1(11) )
<=>
1 = 1(37) - 2(13) - 5(13) + 5(11)
<=>
1 = 1(37) - 7(13) + 5(11)

Now remember, 37 and 13, are the "main players" in this problem and 2 and 11 are the "supporting players" or "buliding blocks" or "intermediate steps." So we keep 37's and 13's but we eliminate the 11 again using a substitution we've already used.

1 = 1(37) - 7(13) + 5(11)
<=>
1 = 1(37) - 7(13) + 5( 1(37) - 2(13) )
<=>
1 = 1(37) - 7(13) + 5(37) - 10(13)
<=>
1 = 6(37) - 17(13)

So now this little "coefficient" of 13 is it's inverse. Notice that we have NEGATIVE 17. So let's add 37 to get a number between 0 and 36, and we see that 37 - 17 = 20. So the inverse of 13 is 20.

And there you go.

If you have any other questions feel free to contact me.

Answer 2

ya im not sure I see the question here either, I understand euclids algorithm pretty well from what I just read ....
http://www.cut-the-knot.org/blue/Euclid.shtml
and
http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html

13 in Z37 is the part that doesnt make sense to me.
what are the first two stages?
1 = 11 - (5 * 2)
= 11 - 5(13 - 11 * 1)
= 11 - 5(13 - 11(11 - (5 * 2)) ???

ohhh, after writing all this i see what darthsherwin wrote
nice answer darthsherwin thumbs up

Answer 3

You run the Euclidean set of rules "backwards". i've got have been given to redo the Euclidean set of rules to show you what I recommend: 231 = 2*80 one + sixty 9 80 one = a million*sixty 9 + 12 sixty 9 = 5*12 + 9 12 = a million*9 + 3 Now this final equation provides us 3 as a linear combination of 12 and 9. the previous one has 9 as a mix of sixty 9 and 12, so we are able to get 3 as a mix of sixty 9 and 12, etc: 3 = 12 - 9 9 = sixty 9 - 5*12 => 3 = 12 - (sixty 9 - 5*12) = 6*12 - sixty 9 12 = 80 one - sixty 9 => 3 = 6(80 one - sixty 9) - sixty 9 = 6*80 one - 7*sixty 9 sixty 9 = 231 - 2*80 one => 3 = 6*80 one - 7(231 - 2*80 one) = 20*80 one - 7*231 So 3 = 20*80 one - 7*231. Chickity verify it.

Answer 4

can you state the question more clearly ?
13 in Z37 doesnt say much.

the only think i can come up with is that 13 is an element of the group Z mod 37, but that is not a question.
.
do you want to find 2 numbers x and y such that 1 = 13x + 37y ?