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.
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.
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 .
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^{2} = y (a "square root of y").
now, let's look at what this might mean, in say, the integers mod 6:
0^{2} = 0 (mod 6)
1^{2} = 1 (mod 6)
2^{2} = 4 (mod 6)
3^{2} = 9 = 3 (mod 6)
4^{2} = 16 = 4 (mod 6)
5^{2} = 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^{4} (since 1/2 is 4 (mod 7)).
0^{2} = 0 (mod 7)
1^{2} = 1 (mod 7)
2^{2} = 4 (mod 7)
3^{2} = 2 (mod 7)
4^{2} = 2 (mod 7)
5^{2} = 4 (mod 7)
6^{2} = 1 (mod 7)
note the only squares are 0,1,2, and 4. now:
0^{4} = 0^{2} = 0 (mod 7)
1^{4} = 1^{2} = 1 (mod 7)
2^{4} = 4^{2} = 2 (mod 7)
3^{4} = 2^{2} = 4 (mod 7)
4^{4} = 2^{2} = 4 (mod 7)
5^{4} = 4^{2} = 2 (mod 7)
6^{2} = 1^{2} = 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^{2} = a, and if we define a^{1/2} to be a^{4}, 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} = 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^{2} = 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).
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".
Exactly what that would normally mean by - the number, y, sucy that .What about his notation:
Yes, it is, exactly the same.Is this notation applied the same as 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.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?
You need to go back and review modular multiplication!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!