How to calculate $2 ^ {-1} \pmod{10}$

Question

I want to know how to compute the inverse of a number when the module is composite and the number is not coprime.

Can anyone give me the options with an example of how to compute with $2 ^ {-1} \pmod{10}$?

Is there a way to do factorisation or some similar technique that ends with the same result like: $1/9 \pmod{10} = 1/3 \times 1/3 \pmod{10}$ and because 3 is comprime of 10 then is possible?

Thanks

Answer 1

There is no answer. You would be looking for what to multiply $2$ by to get $1$. Just like in the integers, there is no such number. The integers modulo $10$ form a ring (with zero divisors) and there is no guarantee you can divide in one of those.

Answer 2

Note that since $\gcd(10,2)=2$ by Bezout's identity for any $a,b \in \mathbb{Z}$

$$a\cdot 10+b\cdot 2 \equiv 0 \pmod 2$$

then we can't find $a,b$ such that

$$a\cdot 10+b\cdot 2 = 1$$

and therefore $2$ is not invertible $\pmod{10}$.

More in general the modular equation

$$x\cdot n \equiv 1 \pmod m$$

has solution if and only if $\gcd(m,n)=1$.

Answer 3

Here a general fact and a possibly useful idea to find quickly a multiplicative inverse.

Let's $m$ denote the module and $x,y$ integers. Note that

$$x\cdot y \equiv 1 \mod m \Leftrightarrow x\cdot y - 1 = k\cdot m \Leftrightarrow x\cdot y - k\cdot m = 1 \Leftrightarrow (x,m) = (y,m) = 1$$

So, in your example that's not the case.

Concerning how to find the inverse note that provided that $x$ and $m$ are coprime according to Euler's theorem you have $$x^{\varphi(m)} \equiv 1 \mod m \Rightarrow x^{-1}\equiv x^{\varphi(m)-1} \mod m$$

Answer 4

Suppose that you could some $x \in \mathbb{Z}_{10}$ such that $2^{-1} = x\pmod{10}$, or equivalently (multiplying both sides by $2$): $1 = 2x \pmod{10}$. Multiplying both sides by $5$ gives $5 = 10x = 0 \pmod{10}$ which is a contradiction.

So no such $x$ exists.