mod of minus power 1

Question

I am fully aware on how to perform mod calculation. The issue now is that when I have this

$2^{-1} \bmod 10$. How to do this? Is there any formula for this?

Answer 1

We say that $b=a^{-1}\pmod{n}$ (for integers $a,b,n$) when $ab=1\pmod{n}.$ In this case, $b=2^{-1}\pmod{10}$ when $2b=1\pmod{10}.$ Does any such integer $b$ exist? Why (not)?

Answer 2

The notation $a^{-1} \pmod{n}$ is the inverse of $a$ modulo $n.$ $a^{-1}$ is the number modulo $n$ satisfying $$a \cdot a^{-1} \equiv 1 \pmod{n}.$$ (Just like how the inverse of a real number $x$ is the number $x^{-1}$ satisfying $x \cdot x^{-1} = 1.$) Notice that $a^{-1}$ is implied to be unique; it can be proven that a number $a$ cannot have more than one inverse modulo $n.$

For example, since $3 \cdot 7 \equiv 1 \pmod{10},$ $3^{-1} \equiv 7 \pmod{10}$; since $3 \cdot 4 \equiv 1 \pmod{11},$ $3^{-1} \equiv 4 \pmod{11}.$ Another example is that $1 \cdot 1 \equiv 1 \pmod{n}$ for any $n,$ so $1$ is its own inverse modulo any positive integer $n.$ Similarly, $-1 \cdot -1 \equiv 1 \pmod{n}$ for any $n,$ so $-1$ is its own inverse also.

However, in your case there is no inverse: if there was a number $d = 2^{-1}$ so that $2d \equiv 1 \pmod{10},$ then $$2d = 10k+1$$ for some $k.$ The left-hand side is even, but the right-hand side is odd, a contradiction.

In general, $a$ has an inverse modulo $n$ if and only if $\gcd(a, n) = 1.$

Answer 3

Hint $\ $ If $\ bc\ $ has a common factor $\,c > 1\,$ with the modulus $\,nc\,$ then $\,bc\,$ is not invertible:

$\quad {\rm mod}\ nc\!:\,\ a\equiv (bc)^{-1}\!\iff abc\equiv 1\iff nc\mid abc-1\,\Rightarrow\,c\mid 1,\ $ contra $\ c > 1$

Conversely, $\,\gcd(n,b)=1\overset{\rm Bezout}\Rightarrow\,\exists\,c,a\!:\ nc\!+\!ab = 1\,\Rightarrow\,{\rm mod}\ n\!:\ ab\equiv 1\,\Rightarrow\, a\equiv b^{-1}$

Remark $\ $ Inverses are always unique when multiplication is associative and commutative. Indeed, if $\,b\,$ has two inverses $\,\color{}a\,$ and $\,\color{}a'\,$ then they are provably equivalent as follows

$$\begin{eqnarray} &&\qquad\quad\, \color{#0a0}{ba'}\!\equiv 1 \equiv \color{#c00}{ab} \\ \Rightarrow\, && \color{}a\, \equiv\, \underbrace{a(\color{#0a0}{ba'})\,\ \equiv\,\ (\color{#c00}{ab})a'}_{\rm\large associativity}\equiv\, \color{}{a'}\end{eqnarray}\qquad\qquad\qquad$$