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