Results 1 to 5 of 5

Math Help - Modular Arithmetic Notation

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    156

    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:

    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. 4^{-1} \mod 7 = 2).

    What about his notation:

     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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Modular Arithmetic Notation

    Quote Originally Posted by joatmon View Post
    What about his notation:

     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 y^b = x.

    Quote Originally Posted by joatmon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,973
    Thanks
    1638

    Re: Modular Arithmetic Notation

    Quote Originally Posted by joatmon View Post
    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:

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

    What about his notation:

     y = x^{1/b}
    Exactly what that would normally mean by x^{1/b}- the number, y, sucy that 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 3^{-1}= \frac{1}{3}= 5 (mod 7) and, of course, because 5^2= 25= 3*7+ 4= 4 (mod 7), 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!
    Last edited by HallsofIvy; August 11th 2012 at 04:34 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular arithmetic help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2011, 05:50 AM
  2. Some modular arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2010, 11:41 AM
  3. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 12:17 PM
  4. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM
  5. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 15th 2006, 07:07 PM

Search Tags


/mathhelpforum @mathhelpforum