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$ = $2018 * 56 + 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 $271 * t ≡ 1 (mod 2018)$, 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 $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...