1
$\begingroup$

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

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

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

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

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$

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

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

$\endgroup$
  • $\begingroup$ Thank you for your comment. So, is there any bridge between 5.5 and 12 in this case? $\endgroup$ – mallea Jul 14 '19 at 14:02
  • 2
    $\begingroup$ None whatsoever. $\endgroup$ – José Carlos Santos Jul 14 '19 at 14:02
  • 1
    $\begingroup$ $11\equiv -2\bmod 13\implies {11\over 2}\equiv -1\equiv 12\bmod 13$ $\endgroup$ – user645636 Jul 14 '19 at 14:24
  • 1
    $\begingroup$ it can, but I was more just turning odds into their even equivalents mod an odd number. $\endgroup$ – user645636 Jul 14 '19 at 14:31
  • 1
    $\begingroup$ @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}}\ \ $ $\endgroup$ – Bill Dubuque Jul 14 '19 at 16:47
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. $\endgroup$ – Bill Dubuque Jul 16 '19 at 22:03
  • $\begingroup$ It's not from me. thank you for your answer! Btw, is it possible to generalize your approach using ceiling and flooring? $\endgroup$ – mallea Jul 17 '19 at 1:38
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jul 17 '19 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.