Ask your own question, for FREE!
Mathematics
OpenStudy (anonymous):

how do you find the invers of [5] in Zsub10 @MIT 18.02 Multiva…

OpenStudy (anonymous):

what is the gcd(5, 10)?

OpenStudy (anonymous):

[5]\[\in \mathbb{Z} _{10}\] express as [b] where 1<= b <m

OpenStudy (anonymous):

5

OpenStudy (anonymous):

So, because the gcd(5,10) is not 1, 5 doesn't have an inverse mod 10.

OpenStudy (anonymous):

i guess a better way to put it is, there is no solution to the equation:\[5x\equiv 1\mod 10\]since the gcd of 5 and 10 is 5, and 5 doesn't divide 1.

jimthompson5910 (jim_thompson5910):

you can see that there is no inverse to 5 since there are no solutions to 5x = 1 (mod 10)

jimthompson5910 (jim_thompson5910):

5x will either be equal to 5 mod 10 or it will be equal 0 mod 10

OpenStudy (anonymous):

what about [5]∈Z47

OpenStudy (anonymous):

gcd=1

OpenStudy (anonymous):

so there is an inverse. now we gotta find it lol >.<

OpenStudy (anonymous):

do you know about Bezout's Identity by any chance? if you have gcd(a,b)=1, then there exist some integers x, y such that:\[ax+by=1\]? this can help you find inverses sometimes.

OpenStudy (anonymous):

LOL, ya but how, i've been trying to understand this through the slides, but they are very vague, and alot of blanks.... so help is needed

OpenStudy (anonymous):

ya

jimthompson5910 (jim_thompson5910):

5x = 1 (mod 47) 10*5x = 10*1 (mod 47) 50x = 10 (mod 47) 3x = 10 (mod 47) 16*3x = 16*10 (mod 47) 48x = 160 (mod 47) 1x = 160 (mod 47) x = 160 (mod 47) x = 19 (mod 47) So the inverse of 5 mod 47 is 19 mod 47

OpenStudy (anonymous):

So because (5,47)=1, there exists an x and y such that:\[5x+47y=1\] if we can find those integers x and y, then x would be the inverse. ....oh wow jim's way is so much faster lol

jimthompson5910 (jim_thompson5910):

it depends on the values really, but in general I find it to be much faster

OpenStudy (anonymous):

jim, i dont understand what you did :( where did all those numbers come from

OpenStudy (anonymous):

Sometimes you can eyeball it. Note that 47*2=94, which is one shy of a multiple of 5. 19*5=95, which is congruent to 1 mod 47. to the inverse is 19.

OpenStudy (anonymous):

so*

jimthompson5910 (jim_thompson5910):

I started with 5x = 1 (mod 47) and then multiplied both sides by 10 because I wanted to get that 5 as close as possible to 47 (since 50 is really close to 47)

jimthompson5910 (jim_thompson5910):

after doing that, I got 50x = 10 (mod 47) which reduces to 3x = 10 (mod 47) (since 50 = 3 (mod 47))

jimthompson5910 (jim_thompson5910):

I then repeated those last steps to convert 3x = 10 (mod 47) into x = 19 (mod 47)

jimthompson5910 (jim_thompson5910):

the beauty of the method is that the left side coefficient will reduce in magnitude since you're getting closer to the modulus with each iteration

jimthompson5910 (jim_thompson5910):

after a certain number of steps, the coefficient will be 1 leaving you with 1x = k (mod n)

OpenStudy (anonymous):

ahhhh i see now, thx

jimthompson5910 (jim_thompson5910):

yeah it's a bit weird and takes some time to get used to

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!