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

what is the gcd(5, 10)?

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

5

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

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.

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

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

what about [5]∈Z47

gcd=1

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

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.

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

ya

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

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

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

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

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.

so*

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)

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

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

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

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

ahhhh i see now, thx

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

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