How can we better understand multiplicative inverse modulo something?

Question

How can we intuitively understand modulo multiplicative inverse?

Suppose we have an ring $\mathbb{Z}_{13}= \{0, 1, 2, 3, \ldots, 12\}$.

Each element except zero has corresponding multiplicative inverse.

Below is the mapping of inverse.

1 $\rightarrow$ 1

2 $\rightarrow$ 7

3 $\rightarrow$ 9

4 $\rightarrow$ 10

5 $\rightarrow$ 8

6 $\rightarrow$ 11

7 $\rightarrow$ 2

8 $\rightarrow$ 5

9 $\rightarrow$ 3

10 $\rightarrow$ 4

11 $\rightarrow$ 6

12 $\rightarrow$ 12

Now, I want to consider division by 2, which here means that multiplication by 7. However, some integer multiplied 7 becomes acutally the same result as division by 2 over real number field. For example, the following holds.

4 * 7 = 28 = 2 mod 13; 6 * 7 = 42 = 3 mod 13; etc.

On the other hand, other values do not produce the same result over real number fields.

For example, 5 * 7 = 35 = 9 mod 13 (I want this value to be 2 or 3 since 5/2 = 2.5)

7 * 7 = 49 = 10 mod 13 (I want this value to be 3 or 4 since 7/2 = 3.5).

Why some values produce the same result as over the real number field, and the others do not??

Answer 1

Operations mod $n$ aren't guaranteed to preserve the order inherited from the reals.

So the fact that in $\mathbb{R}$, we have $$2 < {\small{\frac{5}{2}}} < 3$$ doesn't imply $$2 < ({\small{\frac{5}{2}}}\;\text{mod}\;13) < 3$$ However what is true is that, working mod $13$, we have $$ {\small{\frac{5}{2}}} = 2+{\small{\frac{1}{2}}} = 2+7 = 9 \qquad\;\;\; $$ and also $${\small{\frac{5}{2}}} = 3-{\small{\frac{1}{2}}} = 3-7 = -4 = 9$$

Answer 2

Because that doesn't work even for the number $2$. Note that $11\times7=77\equiv12\pmod{13}$. However, $\frac{11}2=5.5$, which is not near $12$.

Answer 3

Note that $5 \times 7 = 35 = 9 \pmod{13}$, not 11 as you claimed in your question -- and, given this, it might help to observe that we can also think of $2.5$ as $2.5 = 2 + .5 = 2 + 2^{-1} = 2 + 7 = 9 \pmod{13}$.

Answer 4

If $b$ is invertible mod $c$, $ab^{-1} \equiv c \mod p$ is equivalent to $a \equiv b c \mod p$, and this means $a = b c + k p$ for some integer $k$. Sometimes you'll have $k = 0$, so $a = b c$ and $c = a/b$ (as integers), sometimes you won't.

Answer 5

When your modulus is a prime number like $13$ you actually have a field and you may define fractions within your field.

For example $7=1/2$ and $10=1/4$ If you multiply $7\times 7=49=10$ you notice that it is the same as $$1/2 \times 1/2 =1/4$$

The problem which puzzles you is confusing the field of equivalency classes with the field of real numbers.

In the field of equivalency classes you have $$5/2 =5\times 7=9$$

Now if you multiply $9\times 2$ you get $18$ which is $5$ as it should be.

Note that $2.5$ makes sense in real field but you do not have a class of $2.5$ mod $13$ instead you have class of $9$ which serves well as $5/2$

Answer 6

What you seek is generally impossible. Suppose that $\,b\,$ is invertible $\!\bmod n,\,$ i.e. $\,\gcd(b,n)=1\,$ and let's calculate the fraction $\,a/b = ab^{-1}\pmod{\! n},\,$ where $\, 0 < a,b < n$.

By division $\,a = q\,b+r\ $ thus $\bmod n\!:\,\ a/b\equiv ab^{-1} \equiv (qb+r)b^{-1}\equiv q + \color{#c00}{rb^{-1}}$

When $\,r = 0\,$ we get $\!\bmod n\!:\ (qb)/b\equiv q,\,$ same as in $\Bbb R,\,$ when $\,a/b\in\Bbb Z\,$ is an exact quotient.

Else $\,\color{#0a0}{0<r<b}\,$ and you want $\,\color{#c00}{rb^{-1}}\equiv 0\,\ {\rm or}\,\ 1\, \Longrightarrow\, \color{#0a0}{r\equiv 0\,\ {\rm or}\,\ b},\,$ contradiction.

Note $ $ It can be true for fractions with $\,a,b > n\,$ if they reduce to exact quotients $(r= 0),\,$ e.g.

$$\bmod 13\!:\ \ \dfrac{13}{27}\equiv \dfrac{0}1 = \left\lfloor \dfrac{13}{27}\right\rfloor,\ \ \dfrac{14}{27}\equiv \dfrac{1}1 = \left\lceil \dfrac{14}{27} \right\rceil\qquad\qquad\qquad $$