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

Question

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.

Answer 1

We have $$1=2018(56)+271(-417)$$

Hence $$1\equiv 2018(56)+271(-417) \pmod{2018}$$

$$1\equiv 271(-417) \pmod{2018}$$

Hence $-417 \equiv 2018-417\pmod{2018}$ is its inverse.