1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular arithmetic

  1. Oct 17, 2008 #1
    1. The problem statement, all variables and given/known data

    Find x for

    ax = 1 (mod m)

    a) a = 15 , m = 31
    b) a = 6, m = 93
    c) a = 15, m = 20

    if possible.


    (The equal sign above is equivalence in modular arithmetic)


    2. Relevant equations



    3. The attempt at a solution

    a) gcd(31,5) = gcd( 31 - 2*15, 15) = 1

    thus (1)(31) + (-2)(15) = 1

    and (-2) * 15 = 1 (mod 31)

    i dont understand how I can find x since multiplying by -2 yields a number smaller than the modulus

    b) gcd(93,6) = 3

    no solution because gcd =/= 1

    c) gcd(20,15) = 5

    no solution


    Could somebody please help me out with these problems. It's my first time doing modular arithmetic and the book has only two examples.

    Thank you!
     
    Last edited by a moderator: Oct 17, 2008
  2. jcsd
  3. Oct 17, 2008 #2
    Is -30 (mod 31) not 1? Not too sure what you're asking.
     
  4. Oct 17, 2008 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    2(15)= 30 is "smaller than the modulus" but -2(15)= -30= (-1)(31)+ 1 so -2(15) is equal to 1 mod 31. Strictly speaking, the "numbers" in modulo arithmetic are equivalence classes of integers having the same remainder when multiplied by the modulus- one of which is a non-negative number less than the modulus. 1, for example, is in the set also containing 31+1= 32, -31+1= -30, 2(31)+1= 63, etc. -2 is in the same set as 31- 2= 29.


    Both b and c are correct. If 6x= 1 (mod 93) then 6x= 93n+ 1 for some integer n or 6x- 93= 1. As you say, since both 6 and 93 have a factor of 3, 6x- 93= 3(2x- 31) has a factor of 3 no matter what x is and so cannot be equal to 1. Similarly, if 15x= 1 (mod 20), then 15x= 20n+ 1 or 15x- 20n= 1 for some integer n. Since 15 and 20 both have a factor of 5, 15x- 20n= 5(3x- 4n) is a multiple of 5 and cannot be equal to 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular arithmetic
  1. Modular arithmetic (Replies: 3)

  2. Modular arithmetic (Replies: 3)

  3. Modular arithmetic (Replies: 6)

  4. Modular Arithmetic (Replies: 23)

  5. Modular arithmetic (Replies: 3)

Loading...