7
$\begingroup$

The book I'm reading defines the multiplicative inverse of $a\pmod N$ as $x$, such that $ax \equiv 1\pmod N$. It then states not all numbers have a multiplicative inverse, such as $2 \pmod 6$. It states that for a multiplicative inverse to exist, $N$ and $a$ have to be co-prime.

But wouldn't the multiplicative inverse just be the reciprocal? And since every number has a reciprocal, wouldn't every number have a multiplicative inverse?

I.e It states $2 \pmod 6$ does not have a multiplicative inverse. But what about $\frac{1}{2}\pmod 6$? Doesn't this qualify as the multiplicative inverse since $\frac{1}{2}\pmod 6 \times 2\pmod 6 = 1 \pmod 6$?

What am I misunderstanding here?

  • 0
    @J.D. I didn't realize that the OP didn't grasp the content of your comment (well, *answer*, now). Good catch!2012-04-13

5 Answers 5

4

There are two problems, one each depending on what $\frac{1}{2}$ means.

  1. We can define $\frac{1}{a}$ to be "the [unique] number such that $a\times\frac{1}{a}=1$, if it exists" in whatever system we are working on (that is, "number" here would mean "number modulo $N$"). But then you cannot assume that such a thing as $\frac{1}{2}\pmod{N}$ exists in the first place. You must prove it exists.

    Note that they don't always exist: for example, $2$ has no multiplicative inverse in the integers either.

    In this situation, it is true that $\frac{1}{2}\pmod{6}$ is a multiplicative inverse of $2\pmod{6}$, if it exists. But in fact, no such thing exists. Just like an even prime number greater than $2$ would be congruent to $0$ modulo $2$ if it existed, but no such thing exists.

  2. If by $\frac{1}{2}$ you mean the rational number $\frac{1}{2}$, then $\frac{1}{2}\pmod{6}$ makes no sense in the integers modulo $6$: we only allow integers! That is, when we write things like $a\pmod{N}$, we are implicitly asserting that $a$ is an integer. We cannot do that with $\frac{1}{2}$.

    To see that there cannot exist an integer $x$ such that $2x\equiv 1\pmod{6}$, note that $2x-1$ is always odd, so it is never a multiple of $6$; hence, $2x$ can never be congruent to $1$ modulo $6$, no matter what integer $x$ is.

2

One thing you're missing is that you shouldn't be referring to such alleged objects as $2\bmod 6$, etc. $ \text{Right:}\quad (x \equiv y)\pmod n $ $ \text{Wrong:}\quad x \equiv \Big( y \bmod n \Big) $

To say that $x$ and $y$ are mod-$n$ congruent to each other means their difference is a multiple of $n$. Thus for example, $(69\equiv 62) \pmod 7$.

Now observe that $(3\cdot5 \equiv 1)\pmod 7$, so $3$ and $5$ are each other's mod-$7$ reciprocals.

  • 1
    It is a bit peculiar to write the objects as $x\pmod{n}$, but it does make sense in a certain way. Usually people would write $[x]$ or $\overline{x}$ as the image of $x$ in the quotient ring $\mathbb{Z}/n\mathbb{Z}$ (i.e., $[x]$ would be the set of all numbers equivalent to $x$ modulo $n$, sometimes written $x+n\mathbb{Z}$), so it's not unreasonable notation to my eye. However, you make a good point because people tend to get the impression that mod is an operator without realizing it as a relation.2015-04-30
1

The rational number $1/2$ is not allowed as a value of $x$.

Only integers are allowed for modular arithmetic (in the context of the question).

But wouldn't the multiplicative inverse just be the reciprocal? And since every number has a reciprocal, wouldn't every number have a multiplicative inverse?

This is only true for fields like the real numbers $\mathbb{R}$ or complex numbers $\mathbb{C}$, where every non-zero "number" has a "reciprocal".

1

I guess we need layman's terms here for OP's benefit.

What you are missing here: is that in arithmetic modulo 6, the only set of numbers you have is $\{0, 1, 2, 3, 4, 5\}.$ There is no $\frac{1}{2}.$ You are no longer working with all numbers. You're only working with a restricted subset, namely: $0, 1, 2, 3, 4, 5.$ (more formally $\{[0], [1], \ldots [5]\}$ where $[x] = \{ y : y \equiv x \pmod{6} \}$)

I will steal these pictures from Wolfram|Alpha: that's arithmetic $\pmod{6}.$

  • 0
    (See my comment on the OP...)2012-04-13
0

The use of $a^{-1}$ instead of $\dfrac 1a$ (or $\div a$) is often but not always required. Basically, it's complicated.

With a little numerical manipulation, both ways will make sense; but, you still need to be careful.

For example, we find $3^{-1} \equiv 9 \pmod{13}$ (Note that $3 \times 9 \equiv 27 \equiv 1 \pmod{13}$). In the following cases, I will show that some times multiplying by $3^{-1} \equiv 9 \pmod{13}$ is appropriate, and some times dividing by $3$ is appropriate.

(1.) Consider the equivalence, $3x \equiv 12 \pmod{13}.$

So we can compute $ x \equiv 9 \times 12 \equiv 108 \equiv 4 \pmod{13}$. But it would be silly to do all of that work when we can see that $12 \div 3 = 4$.

(2.) Consider the equivalence, $3x \equiv 10 \pmod{13}.$

Since $10 \div 3$ is not an integer; we can't use that method. By repeatedly adding $13$, we see that $10 \equiv 23 \equiv 36 \pmod{13}$ and $36 \div 3 =12.$ So $x \equiv 12 \pmod{13}$. This method is only practical though for very small moduli. It would be much more efficient, usually, to just compute $x = 3^{-1}\times 10 \equiv 9 \times 10 \equiv 90 \equiv 12 \pmod{13}$.

There is a theorem that states that the equivalence $ax \equiv b \pmod c$ if and only if $\gcd(a,c) \mid b$. If there is a solution, then the equivalence reduce to $\dfrac ag x \equiv \dfrac bg \pmod{\dfrac cg}$ where $g = \gcd(a,c)$.

(3.) Consider the equivalence, $3x \equiv 12 \pmod{15}.$

In this case, $\gcd(3,15)=3 \mid 12$, so there is a solution and we find $x \equiv 4 \pmod{5}.$

(4.) Consider the equivalence, $3x \equiv 10 \pmod{15}.$

In this case, $\gcd(3,15)=3 \not \mid 10$, so there is no solution.