 better be one - otherwise we can't be sure that a solution exists. Proceed as follows: 3220 = 40*79 + 60 79 = 1*60 + 19 60 = 3*19 + 3 19 = 6*3 + 1 3 = 3*1 + 0 The last nonzero remainder is the gcd. Thus gcd(79,3220) = 1 (as expected). Now write this gcd (one) as a linear combination of 19 and 3220 by working back up the tree that we just created: The next to the last line gives: 1 = 19-6*3 = 19-6*(60-3*19) = 19*19 - 6*60 = 19*(79-60) - 6*60 = 19*79 - 25*60 = 19*79 - 25*(3220-40*79) = 1019*79 - 25*3220 Thus 1019*79 - 25*3220 = 1 Now do "mod 3220" on both sides to obtain: 1019*79 = 1 mod 3220 (the term that contains 3220 goes away because 3220 = 0 mod 3220). Thus d = 1019. So the inverse of 79 mod 3220 is 1019. Another way of saying this is that 79*1019 will be one more than a multiple of 3220. This can be generalized quite easily if you're interested in teaching the algorithm to a computer. The Extended Euclidean Algorithm is basically a set of instructions that explain how to generate a number from the previous numbers (using the relations that are obvious from the construction of the tree that we used above to find the gcd). >Since I can't solve the above equation I have a feeling I'll be >having trouble with this also: >C = M^e mod n >Any special way to solve this? If I can put values in all of them >except C how do I solve it. If you know everything except C, just compute M^e and reduce mod n. All you're doing is finding the remainder upon division by n. See below for an explanation of how to compute 40 mod 29. >An example I found online showed this: >Solution to linear congruence 11x = 5 ( mod 29 ) >Multiply both sides by the inverse of 11 mod ( 29 ): >8 * 11x = 8 * 5 ( mod 29 ) >x = 40 = 11 ( mod 29 ) > >My question here is how is the inverse of 11 the number 8? >How come 40 = 11 ( mod 29 ), shouldn't that be 1? 8 is the inverse of 11 mod 29 because 8*29 = 1 mod 29. Another way of saying this is 8*29 is one more than a multiple of 29. You can either see this by inspection or, if you need to compute the inverse of 11 mod 29, proceed as in the first part above. 40 = 11 mod 29 because 40 is 11 more than a multiple of 29. That is, when we divide 40 by 29, we get a remainder of 11: 40 = 1*29 + 11 ^^ the remainder I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum