Question

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

Answer 1

what is the gcd(5, 10)?

Answer 2

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

Answer 3

5

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

what about [5]∈Z47

Answer 9

gcd=1

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

ya

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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.

Answer 19

so*

Answer 20

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)

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

ahhhh i see now, thx

Answer 26

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