# Thread: which numbers exist in modular arithmetic? negative exponents???

1. ## which numbers exist in modular arithmetic? negative exponents???

I have a question about which numbers exist and which ones don't in modular arithmetic.

The questions from the textbook are in red. The solutions from the manual are in blue (but got scanned as purple). My comments are green.

2. In $\displaystyle \mathbb{Z}_n$, the inverse $\displaystyle x^{-1}$ of x is an element of $\displaystyle \mathbb{Z}_n$ such that if you multiply it by x (mod n), the answer is 1.

So in $\displaystyle \mathbb{Z}_5$ the inverse of 2 is $\displaystyle 2^{-1} = 3$, because when you multiply 2 by 3 you get 6, which is equal to 1 (mod 5).

But in $\displaystyle \mathbb{Z}_4$, $\displaystyle 2^{-1}$ does not exist, because whatever you multiply 2 by you will always get an even number, so the answer can never be equal to 1 (mod 4).

In general, an element x in $\displaystyle \mathbb{Z}_n$ will have an inverse provided that the numbers x and n have no common factor.

3. Originally Posted by Opalg
In $\displaystyle \mathbb{Z}_n$, the inverse $\displaystyle x^{-1}$ of x is an element of $\displaystyle \mathbb{Z}_n$ such that if you multiply it by x (mod n), the answer is 1.
What is the logic and/or intuition behind this rule?

4. Working in $\displaystyle \mathbb{Z}_5$, the notation $\displaystyle 3^{-1}$ simply means the inverse of 3, which means the number $\displaystyle s$, such that $\displaystyle 3s\equiv 1\pmod{5}$. In this case, we have $\displaystyle s=2$, since $\displaystyle 3\cdot 2 = 6$, which is 1 mod 5. Short answer, $\displaystyle 3^{-1}=2$.

Generally, when working mod n, the number x has an inverse, iff x and n are relatively prime.

5. Originally Posted by kablooey
Originally Posted by Opalg
In $\displaystyle \mathbb{Z}_n$, the inverse $\displaystyle x^{-1}$ of x is an element of $\displaystyle \mathbb{Z}_n$ such that if you multiply it by x (mod n), the answer is 1.
What is the logic and/or intuition behind this rule?
It's the natural definition of an an inverse. The inverse of any number is what you multiply the number by in order to get 1. Like the inverse of 7 is $\displaystyle \tfrac17$, because $\displaystyle 7*\tfrac17 = 1$. The only difference from ordinary arithmetic is that in $\displaystyle \mathbb{Z}_n$, "multiplication" means "multiplication mod n".

6. it all has to do with the prime factorization of n.

for example, in Z4, 2 is what is called a "zero divisor", because (2)(2) = 4 = 0 (mod 4).

and, as you might expect, "dividing by a zero divisor" is like "dividing by 0", it just doesn't work.

but 5 is prime, which means that every non-zero element of Z5 will have an inverse:

(1)(1) = 1 (mod 5), so 1 is it's own inverse.
(2)(3) = 6 = 1 (mod 5) so 2 and 3 are inverses.
(4)(4) = 16 = 1 (mod 5), so 4 is it's own inverse.

that is: "1/2" can be defined in Z5: it is just 3.

but "1/2" cannot be defined in Z4:

(1)(2) = 2 (mod 4), which is not 1.
(2)(2) = 4 = 0 (mod 4), not 1 either.
(3)(2) = 6 = 2 (mod 4), again, not 1.

no matter what we multply 2 by in Z4, we never get 1. multiplication by 2 in Z4 is a "one-way street", we can't go backwards and "undo it" .

suppose we know that 2x = 2 (mod 4). well, we can't say for sure if x = 1, or if x = 3. this happens precisely because 2 and 4 share a common factor.

7. Originally Posted by kablooey
What is the logic and/or intuition behind this rule?
I'm not sure exactly what you're asking. If you're asking what the use is of this notion of inverse, then the original post is a fine example: You can use inverses to solve modular equations such as 3x = 4 (mod 5).

You know that 2*3 = 1 (mod 5). Hence you can multiply both sides of the congruence 3x = 4 (mod 5) by 2 to obtain

2*3x = 8 (mod 5),

so since 2*3 = 1 (mod 5), and since 8 = 3 (mod 5), this reduces to

1*x = 3 (mod 5), or

x = 3 (mod 5).

Thus knowing the inverse of 3 helped solve the problem.