Thread: 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:



in algebra means that y = 1/x. But in modular arithmetic, it means that y is the modular inverse of x (e.g. ).

What about his notation:



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!

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.

Originally Posted by joatmon

What about his notation:

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 .

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.

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

then y^1/2 would mean a number x with x² = y (a "square root of y").

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

0² = 0 (mod 6)
1² = 1 (mod 6)
2² = 4 (mod 6)
3² = 9 = 3 (mod 6)
4² = 16 = 4 (mod 6)
5² = 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 a⁴ (since 1/2 is 4 (mod 7)).

0² = 0 (mod 7)
1² = 1 (mod 7)
2² = 4 (mod 7)
3² = 2 (mod 7)
4² = 2 (mod 7)
5² = 4 (mod 7)
6² = 1 (mod 7)

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

0⁴ = 0² = 0 (mod 7)
1⁴ = 1² = 1 (mod 7)
2⁴ = 4² = 2 (mod 7)
3⁴ = 2² = 4 (mod 7)
4⁴ = 2² = 4 (mod 7)
5⁴ = 4² = 2 (mod 7)
6² = 1² = 1 (mod 7)

now we are in a position to answer the question:

if we define (mod 7) a^1/2 to be a b such that b² = a, and if we define a^1/2 to be a⁴, are these two definitions the same?

clearly, the answer is "no", for in the first definition 3^1/2 does not exist, whereas 3⁴ = 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 6² = 1 (mod 7), so it makes sense to say: 1^1/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 a^1/b, to come up with a similar meaning for an expression in the integers (mod n).

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:



in algebra means that y = 1/x. But in modular arithmetic, it means that y is the modular inverse of x (e.g. ).

Are you really clear on what means "in algebra"? In any "algebraic structure" (that has a multiplication defined) means y such that xy= 1. That's exactly what 1/x (mod n) means. Whether we call it or , 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".

What about his notation:

Exactly what that would normally mean by - the number, y, sucy that .

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 and, of course, because , . 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!