inverse of a mod

Question

I can't get my head around this: I got this and need to find an inverse for Chinese Remainder Theorem

$$2x=1 \mod 5$$

$$S_1 \Rightarrow 2^{-1}\cdot 2\cdot x=2^{-1} \cdot 1 \mod 5$$

$$S_2 \Rightarrow x = 2^{-1} \mod 5$$

I understand that in order to get the inverse of this going I will need to eradicate the $2$ on the left hand side $(S_1)$, so next I come up with $S_2$ but now what?

What should I compute and in which direction?

Answer 1

Which number makes $2\cdot x\equiv 1 \pmod5$? You can have $4$ guesses ($0$ excluded).

Modulo $5$ we have only $0,1,2,3,4$. We can also use $-2$ and $-1$ instead of $3$ and $4$, because if $a\equiv b \pmod m$ -- that is, they give the same remainder mod $m$, or easiest: $m|\,b-a$ -- then for any $n$, $\ an\equiv bn \pmod m$.

So, we have the following: $2\cdot 0=0,\ 2\cdot 1=2,\ 2\cdot 2=4\equiv -1,\ 2\cdot 3=6\equiv 1,\ 2\cdot 4=8\equiv 3 \pmod 5$.

(Or, using the negative numbers $2\cdot (-2)=-2\cdot 2\equiv -(-1)=1$.) So, $x\equiv 3\equiv -2 \pmod 5$.

In general, by Bezout's identity, we have that a number $a$ has a multiplicative inverse mod $m$ iff $\gcd(a,m)=1$, because then $$1=xa+ym$$ for some $x,y\in\Bbb Z$, and $ym\equiv 0 \pmod m$, so then $x$ is the inverse of $a$ mod $m$. (On the other hand, if $\gcd(a,m)=d>1$ then $d$ will divide all multiples of $a$, and also the remainder mod $m$.)

Answer 2

As Berci said, generally one may employ the Bezout gcd identity to calculate modular inverses. But that is overkill in the "easy inverse" case $\rm\ a^{-1}\ (mod\ an\pm 1)\:$ when the modulus $\rm\: \equiv \pm 1\,\ (mod\ a).\:$ This implies $\rm\:a,m\:$ are coprime, so $\rm\:a^{-1}$ exists $\rm\:mod\ m,\:$ and we can compute it simply as follows

$\rm\quad\ \ mod\ an\!-\!1\!:\ \ 1\ \equiv\ an\ \Rightarrow\ \dfrac{1}a \,\equiv\, \dfrac{an}a \,\equiv\, n$

$\rm\quad\ \ mod\ an\!+\!1\!:\ \ 1\equiv {-}an\:\Rightarrow\:\dfrac{1}a \,\equiv\, \dfrac{-an}a\, \equiv\, -n$

So $\rm\ mod\ 2n\!-\!1\!:\ \dfrac{1}2 \,\equiv\, n,\:$ by $\rm\:a = 2\:$ above. $ $ So $\rm\:n=3\:$ gives $\rm\ mod\ 5\!:\ \dfrac{1}2 \equiv 3,\,$ indeed $\rm\ 2\cdot 3\equiv 1.$

Beware $\ $ One can employ fractions $\rm\ x\equiv b/a\ $ in modular arithmetic (as above) only when the fractions have denominator $ $ coprime $ $ to the modulus $ $ (else the fraction may not uniquely exist, $ $ i.e. the equation $\rm\: ax\equiv b\,\ (mod\ m)\:$ might have no solutions, or more than one solution). The reason why such fraction arithmetic works here (and in analogous contexts) will become clearer when one learns about the universal properties of fraction rings (localizations).

The "easy inverse" case is essentially the case when computing the Bezout identity by the extended Euclidean algorithm requires only one step. It is much wasted effort to execute the algorithm in this simple case (which occurs quite frequently in practice due to the law of small numbers).