Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmatic

  1. Oct 11, 2011 #1
    1. The problem statement, all variables and given/known data

    If I have some fraction, a/b, in Z subscript 5. (Z is an integer Field) How should I go about doing this?


    2. Relevant equations

    I understand that (ab) mod n = ((a mod n)(b mod n)) mod n

    3. The attempt at a solution


    Thus, I am tempted to say that (a/b) mod n = ((a mod n)/(b mod n)) mod n

    However, following that equation, there will be times where I will also end up with a fraction.

    exmaple, ((7 mod 5) / ( 24 mod 5)) mod 5 = (2/4) mod 5
    = 1/2

    So how should I go about solving 7/24 in Z5 or something similar?

    I have a feeling I'm missing something obvious.
     
  2. jcsd
  3. Oct 11, 2011 #2

    Deveno

    User Avatar
    Science Advisor

    you have established that if

    24x = 7 (mod 5) than
    2x = 1 (mod 5).

    the multiplicative inverse of 2 in Z5 is 3:

    (2)(3) = 6 = 1 (mod 5).

    therefore, multiply by 3 to get:

    x = 3 (mod 5).

    i would advise against using "fractional" notation in modular arithmetic, because your intuition about fractions will not generally hold.

    in particular, if the modulus is not prime, divsion by some numbers is not possible (we don't have a field).
     
  4. Oct 11, 2011 #3
    I seem to have a grasp of it now.

    However, using the example (7/24) in Z5

    From "24x = 7 mod 5" to "2x = 1 mod 5"

    I am able to get this by doing:

    ((7 mod 5)/(24 mod 5)) mod 5. so, I get (1/2) mod 5

    hence I achieve the "2x = 1 mod 5"

    Is this the right way to go from 24x = 7 mod 5 to 2x = 1 mod 5 or is it wrong, or is there perhaps a better way?
     
  5. Oct 11, 2011 #4

    Deveno

    User Avatar
    Science Advisor

    what you are doing is the same:

    i just reduced 7 (mod 5) and 24 (mod 5) first.

    when working "mod n", a good first step is to replace every number

    to it's equivalent in {0,1,2,...,n-1}.

    that's one of the purposes of working "mod n", to reduce a large number

    problem, to a smaller number problem.

    the reason you don't want to use fractions, is to avoid the temptation to "cancel", which can lead to errors.

    for example:

    2x = 2 (mod 6) has the solution x = 4, but we can't "cancel the 2's"

    x = 1 (mod 6) does NOT have x = 4 as a solution.
     
  6. Oct 12, 2011 #5
    Deveno is right to warn you about cancellation in modular arithmetic, but in this particular instance it doesn't pose a problem. For any prime p, [itex]\mathbb{Z}_p[/itex] is a field, so every nonzero element has a multiplicative inverse, thus justifying the use of the notation [itex]\frac{1}{x}[/itex]. Since 5 is prime, [itex]\mathbb{Z}_5[/itex] is a field (as you mention in the OP). In general you can use the Euclidean algorithm to find multiplicative inverses mod n.
     
  7. Oct 12, 2011 #6
    Thanks for the help.
     
  8. Oct 12, 2011 #7

    Deveno

    User Avatar
    Science Advisor

    yes, modulo a prime, "fractions" do make sense, and in fact you can treat integers modulo p much the same as "regular numbers" (i.e., the rational numbers) because they form a field.

    you still have to be careful, though, about "dividing by 0", for example, in mod 5, you don't ever want to divide by 10. and it may not be immediately evident that you are dividing by 0 in the integers mod p, because there are "more 0's" (every p-th number) to watch out for.

    also, as a general rule, it is clearer conceptual thinking to think of dividing by b as multiplying by b^-1 (which you can write as 1/b, if you wish). why? well, for one reason, multiplication is associative, but division is not. a/(b/c) is not the same as (a/b)/c, so when dividing, the order you do it in, matters. with multiplication, there is no such difficulty, which (in my opinion) leads to fewer computational errors.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Arithmatic
  1. Modular arithmetic (Replies: 11)

  2. Modular arithmetic (Replies: 1)

  3. Modular arithmetic (Replies: 4)

Loading...