# How can we better understand multiplicative inverse modulo something?

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??

• I think you mean $35=9$, which you'll notice is $22=11\times 2$. similarly, $7=20=2\times 10$. – J.G. Jul 14 '19 at 14:06
• Yeah, that's true. Thank you for your suggestion! I have corrected it – mallea Jul 14 '19 at 14:21

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

• Hi, I found that $\frac{5}{2} \mod 13 = \frac{5 - 13}{2} = -4 \equiv 9 \mod 13$. How can I generalize this?? – mallea Jul 16 '19 at 20:04

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

• Thank you for your clear explanation! – mallea Jul 16 '19 at 19:56
• Thank you for your attention and understanding – Mohammad Riazi-Kermani Jul 16 '19 at 20:20

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

• Thank you for your comment. So, is there any bridge between 5.5 and 12 in this case? – mallea Jul 14 '19 at 14:02
• None whatsoever. – José Carlos Santos Jul 14 '19 at 14:02
• $11\equiv -2\bmod 13\implies {11\over 2}\equiv -1\equiv 12\bmod 13$ – user645636 Jul 14 '19 at 14:24
• it can, but I was more just turning odds into their even equivalents mod an odd number. – user645636 Jul 14 '19 at 14:31
• @mallea There is a "bridge", viz. $\ 5.5 = 5 + \dfrac{\color{#c00}{\bf 1}}2 \equiv 5 + \dfrac{\color{#c00}{14}}2 \equiv 12\pmod{\color{#c00}{\!\!13}}\ \$ – Bill Dubuque Jul 14 '19 at 16:47

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

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.

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

• @Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. – Bill Dubuque Jul 16 '19 at 22:03
• It's not from me. thank you for your answer! Btw, is it possible to generalize your approach using ceiling and flooring? – mallea Jul 17 '19 at 1:38
• @mallea I wasn't sure how you sought to "round", so I gave examples both ways. But the point was to emphasize that it won't work work in many cases. – Bill Dubuque Jul 17 '19 at 1:45