Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
There is no $1/2\pmod 6$: by definition that would be an integer $x$ such that $2x\equiv 1\pmod 6$, and there is no such integer. –  Brian M. Scott Apr 13 '12 at 3:56
3  
"Reciprocal" means "multiplicative inverse", and it only makes sense to write the division symbols "1/2" when the reciprocal of 2 exists (in the ring). –  The Chaz 2.0 Apr 13 '12 at 4:01
    
But the reciprocal of 2 would exist in any ring that has a modulus greater than 1/2 wouldn't it? –  user26649 Apr 13 '12 at 4:04
    
In short, no. I don't know why you are motivated to believe this, but please change your mind ASAP! –  The Chaz 2.0 Apr 13 '12 at 4:09
1  
Thank You. I was unaware that modulus is restricted to integers. Sorry, it was a stupid mistake, I'm just new to all of this –  user26649 Apr 13 '12 at 4:21

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank You, that simplified it a LOT. –  user26649 Apr 13 '12 at 4:22

One thing you're missing is that you shouldn't be referring to such alleged objects as $2\mod 6$, etc. $$ \text{Right:}\quad (x \equiv y)\pmod n $$ $$ \text{Wrong:}\quad x \equiv \Big( y \mod 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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
(See my comment on the OP...) –  The Chaz 2.0 Apr 13 '12 at 4:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.