Modulo multiplicative inverse

287 Views Asked by At

In ax $\equiv$ 1 (mod m) , when gcd(a, m) = 1, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique.

This is written in wikipedia. I am confused because i keep on thinking if a = 2 and m = 3. Then x can be 2,5,8 etc. I know i am missing something but i am unable to get it. I am on my own and thus would be happy if someone can clear my doubt.

2

There are 2 best solutions below

3
On BEST ANSWER

The important idea here is that we are working in the ring $\mathbb{Z}/m$, and questions about uniqueness of inverses should be asked in this context. Taking the $m$ elements of $\mathbb{Z}/m$, there is only one of them that's an inverse to any given $x$.

In your example, all of $2$, $5$, $8$, $11$, $14$ and so on are inverses to $2 (mod 3)$. But they're all equal to $2 (mod 3)$, so as far as $\mathbb{Z}/3$ is concerned that's the only inverse.

0
On

If we have $a=2$ and $m=3$ then we have the equation $2x=1\mod3$, there are multiple solutions to this notably $x=3n+2$ for $n \in \mathbb{Z}$.

Just an edit: Even though there are lots of solutions, there will only be one solution for $\mod3$ and in $\mod3$ there are the numbers $\{0,1,2\}$. Where the only solution to this is $2$.