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?


2 Answers 2


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$.)

  • $\begingroup$ 3? I see where this is headed. if i was to compute $x= 42^{-1} \mod 5$ it would be $42*x = 1 \mod 5 = 3$ ? So this the solution to all my problems today? come on it can't be that simple :D $\endgroup$
    – blacksmth
    Feb 19, 2013 at 10:30
  • $\begingroup$ i love you for your answer. can I propose to you? <3 $\endgroup$
    – blacksmth
    Feb 19, 2013 at 10:36
  • $\begingroup$ Math is very very simple!!! Yes, $3$. Note for $42$ that $42\equiv 2\pmod 5$. It means that in modulo $5$ arithmetic they are regarded equal! So, $42^{-1}=3=8=-2=89478462374623873$, at least modulo $5$. $\endgroup$
    – Berci
    Feb 19, 2013 at 10:37

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).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .