1. ## Modular Arithmetic Notation

As I learn more about modular arithmetic, I come across notation that is used differently than what I am used to from algebra and calculus. For example:

$\displaystyle y = x^{-1}$

in algebra means that y = 1/x. But in modular arithmetic, it means that y is the modular inverse of x (e.g. $\displaystyle 4^{-1} \mod 7 = 2$).

$\displaystyle y = x^{1/b}$

Is this notation applied the same as in algebra? If x and b are positive integers, then does this mean that y will rarely result in an integer like it would be in algebra?

I'm working through a question and have come upon notation like this. In the realm of integers, an equation like this seems to be pointless since it will rarely yield an integer when interpreted like an algebra problem. So, I'm thinking that there must be another interpretation. Can anyone help me (assuming that this makes any sense)?

Thanks!

2. ## Re: Modular Arithmetic Notation

Modular multiplicative inverse - Wikipedia, the free encyclopedia

There are other examples where one notation could mean two different things. For example, a fraction with parentheses around it or a Jacobi symbol.

3. ## Re: Modular Arithmetic Notation

Originally Posted by joatmon

$\displaystyle y = x^{1/b}$
Since 1/b is well-defined for b ≠ 0 in a field (and numbers modulo a prime number form a field), there is no problem with this expression. I believe it also means that $\displaystyle y^b = x$.

Originally Posted by joatmon
I'm working through a question and have come upon notation like this.
It is recommended to scan your book for definitions and notations and post questions precisely and in whole.

4. ## Re: Modular Arithmetic Notation

let's look at a simple example: b = 2.

then y1/2 would mean a number x with x2 = y (a "square root of y").

now, let's look at what this might mean, in say, the integers mod 6:

02 = 0 (mod 6)
12 = 1 (mod 6)
22 = 4 (mod 6)
32 = 9 = 3 (mod 6)
42 = 16 = 4 (mod 6)
52 = 25 = 1 (mod 6)

note that 1 and 4 have "two square roots", and 0 and 3 just have one. furthermore, 2 and 5 don't have ANY square roots. why does this happen?

the main reason is: "2" doesn't have an inverse (mod 6), there is no k with 2k = 1. this is because 2 divides 6, and 6 = 0 (mod 6), so 2 "divides 0". this happens because 6 is *composite*.

if we are talking modulo a prime, then the above situation doesn't occur. 2 *always* has a multiplicative inverse (except...mod 2, but that's a "special case", which you should be on the look-out for).

so let's look at mod 7, which *is* a prime. first we'll look at squares, and then we look at a4 (since 1/2 is 4 (mod 7)).

02 = 0 (mod 7)
12 = 1 (mod 7)
22 = 4 (mod 7)
32 = 2 (mod 7)
42 = 2 (mod 7)
52 = 4 (mod 7)
62 = 1 (mod 7)

note the only squares are 0,1,2, and 4. now:

04 = 02 = 0 (mod 7)
14 = 12 = 1 (mod 7)
24 = 42 = 2 (mod 7)
34 = 22 = 4 (mod 7)
44 = 22 = 4 (mod 7)
54 = 42 = 2 (mod 7)
62 = 12 = 1 (mod 7)

now we are in a position to answer the question:

if we define (mod 7) a1/2 to be a b such that b2 = a, and if we define a1/2 to be a4, are these two definitions the same?

clearly, the answer is "no", for in the first definition 31/2 does not exist, whereas 34 = 4 (mod 7).

if, however a = 0,1,2, or 4, then the two definitions still do not agree: for 6 is certainly a number for which 62 = 1 (mod 7), so it makes sense to say: 11/2 = 6 (using our first definition). but notice NO 4th power is EVER 6 (using our second definition).

the moral of the story is: one just cannot adopt "the usual interpretation" of a quantity like a1/b, to come up with a similar meaning for an expression in the integers (mod n).

5. ## Re: Modular Arithmetic Notation

Originally Posted by joatmon
As I learn more about modular arithmetic, I come across notation that is used differently than what I am used to from algebra and calculus. For example:

$\displaystyle y = x^{-1}$

in algebra means that y = 1/x. But in modular arithmetic, it means that y is the modular inverse of x (e.g. $\displaystyle 4^{-1} \mod 7 = 2$).
Are you really clear on what $\displaystyle x^{-1}= \frac{1}{x}$ means "in algebra"? In any "algebraic structure" (that has a multiplication defined) $\displaystyle x^{-1}= \frac{1}{x}$ means y such that xy= 1. That's exactly what 1/x (mod n) means. Whether we call it $\displaystyle 4^{-1}$ or $\displaystyle \frac{1}{4}$, the value is 2, mod 7, because 2(4)= 8= 1 (mod 7). There really is no difference, except, of course, that it is "modulo n".

$\displaystyle y = x^{1/b}$
Exactly what that would normally mean by $\displaystyle x^{1/b}$- the number, y, sucy that $\displaystyle y^b= x (mod n)$.

Is this notation applied the same as in algebra?
Yes, it is, exactly the same.

If x and b are positive integers, then does this mean that y will rarely result in an integer like it would be in algebra?
No, working "modulo n" we are working with integers from 0 to n- 1 (there are other interpretations of "modulo n" but give the same basic results). For example, 3*5= 1 (mod 7) because 3*5= 15= 2(7)+ 1. So $\displaystyle 3^{-1}= \frac{1}{3}= 5 (mod 7)$ and, of course, because $\displaystyle 5^2= 25= 3*7+ 4= 4 (mod 7)$, $\displaystyle 3^{-2}= 4 (mod 7)$. Note that 4(3)= 12= 7+ 5= 5 (mod 7) and that 5*3= 15= 2*7+ 1= 1 (mod 7) so, again, we have [tex]3^{-2}*3*3= 3^{-2}*3^2= 1[/itex] exactly as it should be.

I'm working through a question and have come upon notation like this. In the realm of integers, an equation like this seems to be pointless since it will rarely yield an integer when interpreted like an algebra problem. So, I'm thinking that there must be another interpretation. Can anyone help me (assuming that this makes any sense)?

Thanks!
You need to go back and review modular multiplication!