Results 1 to 3 of 3

Math Help - Modular Arithmetic examples

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    10

    Modular Arithmetic examples

    Just picked out a few examples from a practice exam.


    1)Solving the equation az=1 mod m

    (a) a=3 m = 10 (ANS = 7)
    (b) a=5 m = 18

    2)Solve the following congruence, equations for x.(Giving the solution in the form a mod m)

    (a) 3x - 1 = 7 mod 10 (ANS = x = 6 mod 10)


    Any chance of a step by step explanation on a few of them .
    Last edited by Ciachyou; November 2nd 2008 at 08:27 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by Ciachyou View Post
    Just picked out a few examples from a practice exam.


    1)Solving the equation az=1 mod m

    (a) a=3 m = 10 (ANS = 7)
    (b) a=5 m = 18
    In fact, you're asked to find the inverse of numbers modulo m.

    Let's do it for these two, I guess they'll give you quite the general idea. The key is to use the extended Euclidean algorithm (you can look for it in google)

    Find z in 3z \equiv 1 \bmod 10

    You know that since 3 and 10 are coprime, you'll have a remainder 1 while continuing doing the algorithm. And this is why it is useful.

    Do the algorithm with 10 and 3 as starting points :
    10=3 \times 3+1
    Hence 1=10-3 \times 3

    You can note that 10-3 \times 3 \equiv -3 \times 3 \bmod 10 because 10 \equiv 0 \bmod 10

    So we have -3 \times 3 \equiv 1 \bmod 10
    z=-3 \bmod 10
    In general, we want z to be the least positive integer satisfying the condition.

    So you can add 10 : z=7



    For the second one, you're looking for z in 5z \equiv 1 \bmod 18
    Algorithm for 5 and 18 :
    18=5 \times 3+3
    My method is to write successively the remainders.
    3=18-5 \times 3

    Now, do the division for 5 and the new remainder, 3.
    5=3 \times 1+2
    \implies 2=5-3

    Division for 3 and the new remainder, 2.
    3=2+1
    \implies 1=3-2

    But we saw that 2=5-3 :
    \implies 1=3-(5-3)=2 \times 3-5
    \implies 1=2 \times (18-5 \times 3) -5=18 \times 2-5 \times 6-5=\boxed{18 \times 2-5 \times 7}

    So we have -5 \times 7 \equiv 1 \bmod 18

    \implies z \equiv -7 \bmod 18 \equiv 11 \bmod 18
    Last edited by Moo; November 2nd 2008 at 12:08 PM. Reason: thanks to Opalg :>
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2008
    Posts
    10
    Thanks, that helped me out alot.
    Got a b+
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help with modular arithmetic please
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2011, 03:50 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 4th 2011, 12:07 AM
  3. Modular arithmetic.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 10th 2011, 06:21 PM
  4. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 19th 2010, 03:47 AM
  5. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2008, 09:47 AM

Search Tags


/mathhelpforum @mathhelpforum