Elementary Number Theory: Solving a Congruence Equation

Question

Deduce a value for $475^{-1}$ mod 2018.

I know that $475^{-1}$ mod 2018 can be written as $475 \equiv 1$ mod 2018. I'm not sure how to find what n is. Should I use the Euclidean Algorithm?

Answer 1

Refer to Bezout’s identity then if $\gcd(475,2018)=1$ we can find by Euclidean algorithm $a,b\in \mathbb{Z}$ such that

$$a475+b2018=1\implies a475=1-b2018$$

and thus $a$ is, by definition, the (an) inverse of 475 mod 2018 and we denote it by

$$a=475^{-1} \pmod {2018}$$

Answer 2

\begin{array}{r|rrrl} & 2018 & 1 & 0 \\ -4 & 475 & 0 & 1 & (4 \times 475 = 1900)\\ \hline -4 & 118 & 1 & -4 & (4 \times 118 = 472) \\ -39 & 3 & -4 & 17 & (39 \times 3 = 117) \\ & 1 & 157 & -667 \end{array}

So $157(2018)-667(475) = 1$

So $475^{-1} \equiv -667 \equiv 1351 \pmod{2018} $

Answer 3

"I know that $475^{−1} \mod 2018$ can be written as $475≡1 \mod 2018$"

Not quite.

$475^{-1} \mod 2018$ refers to the equivalence class of $[x]$ where $x$ is a solution to $475x \equiv 1 \mod 2018$ (if there are any solutions).

So we must solve $475x \equiv 1 \mod 2018$

We can use Euclids algorithm. We need

$475x + 2018k = 1$.

Whoosh... $2018 = 118 + 4*475$ so $118 \equiv -4*475 \mod 2018$.

$475 = 3 + 4*118$ so $3 = 475 - 4*118\equiv 475 + 16*475 \equiv 17*475 \mod 2018$

$118 = 1 + 39*3$ so $1 \equiv 118 -3*39\equiv -4*475 - 39*17*475 \equiv (-39*17 - 4)*475 \mod 2018$.

So $-39*17-4 = -667\equiv 475^{-1} \mod 2018$.

Let's verify: $-667*475 = -316825 = -157*2018 + 1\equiv 1 \mod 2018$.

Answer 4

The inverse of $475\bmod 2018$ is the number that multiplies with $475$ to give $1 \bmod 2018$, so that $475^{-1}\cdot 475 \equiv 1 \bmod 2018$.

You can use the extended Euclidean algorithm to find the inverse of $475\bmod 2018$ (which will also tell you if the inverse exists). Here is my preferred tableau:

\begin{array}{c|c} n & s & t & q \\ \hline 2018 & 1 & 0 & \\ 475 & 0 & 1 & 4 \\ 118 & 1 & -4 & 4 \\ 3 & -4 & 17 & 39 \\ 1 & 157 & -667 & 3 \\ \end{array}

... with each line expressing $n=2018s + 475t$ by suitable combination of the previous two lines ($q$ (for quotient) giving the subtraction multiplier for that line from the line above).

The final line gives $157\cdot 2018 + (-667)\cdot 475 = 1$, and the fact that we can make this equal to $1$ tells us that the numbers are coprime and thus the inverse exists. It also gives us the inverse, since it shows that $(-667)\cdot 475\equiv 1 \bmod 2018$ and thus $475^{-1}\equiv -667\equiv \color{red}{1351} \bmod 431$