- #1
SirEllwood
- 3
- 0
Hi all, ok so below is an example of the Extended Euclidean Algorithm, and i understand the first part perfectly to find the g.c.d.
701 − 2 × 322 = 57,
322 − 5 × 57 = 37,
57 − 37 = 20,
37 − 20 = 17,
20 − 17 = 3,
17 − 5 × 3 = 2,
3 − 2 = 1,
and
1 = 3 − 2
= 6 × 3 − 17
= 6 × 20 − 7 × 17
= 13 × 20 − 7 × 37
= 13 × 57 − 20 × 37
= 113 × 57 − 20 × 322
= 113 × 701 − 246 × 322.
Now on the second part, it is finding the equation of ax +by = 1, which i am generally having to find so i can compute the inverse of a(modb). They have managed to do this in 7 steps. It always takes me like more than twice as many in a really longwinded fashion. Has the example below missed out some steps for the sake of conciseness? I just don't understand how they are doing what they are doing.
For example I would have said
1= 3- 2
1 = (20-17) - (17 - (5x3))
1 = ((57-37) - (37-20)) - ((37-20) - 5(20-17))
etc.
Which is obviously far more longwinded, but equally as methodical. I want to know how to do this more concisely so in an exam it would be far less confusing and time consuming.
Thank you!
701 − 2 × 322 = 57,
322 − 5 × 57 = 37,
57 − 37 = 20,
37 − 20 = 17,
20 − 17 = 3,
17 − 5 × 3 = 2,
3 − 2 = 1,
and
1 = 3 − 2
= 6 × 3 − 17
= 6 × 20 − 7 × 17
= 13 × 20 − 7 × 37
= 13 × 57 − 20 × 37
= 113 × 57 − 20 × 322
= 113 × 701 − 246 × 322.
Now on the second part, it is finding the equation of ax +by = 1, which i am generally having to find so i can compute the inverse of a(modb). They have managed to do this in 7 steps. It always takes me like more than twice as many in a really longwinded fashion. Has the example below missed out some steps for the sake of conciseness? I just don't understand how they are doing what they are doing.
For example I would have said
1= 3- 2
1 = (20-17) - (17 - (5x3))
1 = ((57-37) - (37-20)) - ((37-20) - 5(20-17))
etc.
Which is obviously far more longwinded, but equally as methodical. I want to know how to do this more concisely so in an exam it would be far less confusing and time consuming.
Thank you!