Wednesday, 21 October 2015

discrete mathematics - Determine whether 271 is invertible modulo 2018, and if so find an inverse a.

Here is the question I'd greatly appreciate help on:




(a) Use the Euclidean Algorithm to compute gcd (2018,271) and use that to find integers x and y so that gcd (2018,271) =
2018x+271y.



I've done this part. gcd(2018,271) = 1 = 201856+271(417)



(x=56,y=417)



(I will edit in all of the algorithm's steps if needed!)




I'm having trouble with part (b):



(b) Use part (a) to determine whether 271 is invertible modulo 2018, and if it is invertible, find an inverse a of 271 modulo
2018 so that 0<a<2018. Explain why your answer is an inverse of 271 modulo 2018 using the definition of an inverse
modulo n.



I know that 271 is invertible modulo 2018 if and only if there exists an integer t so that 271t1(mod2018), and that t is an inverse of 271 modulo 2018.



However, I just got this from class lecture and don't really know what this means on a conceptual level, and how to apply it to this question.




Thank you.

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...