Results 1 to 3 of 3

Thread: 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; Nov 2nd 2008 at 07: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 $\displaystyle 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 :
    $\displaystyle 10=3 \times 3+1$
    Hence $\displaystyle 1=10-3 \times 3$

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

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

    So you can add 10 : $\displaystyle z=7$



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

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

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

    But we saw that $\displaystyle 2=5-3$ :
    $\displaystyle \implies 1=3-(5-3)=2 \times 3-5$
    $\displaystyle \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 $\displaystyle -5 \times 7 \equiv 1 \bmod 18$

    $\displaystyle \implies z \equiv -7 \bmod 18 \equiv 11 \bmod 18$
    Last edited by Moo; Nov 2nd 2008 at 11:08 AM. 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: Dec 2nd 2011, 02:50 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  3. Modular arithmetic.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Mar 10th 2011, 05:21 PM
  4. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 19th 2010, 02:47 AM
  5. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 4th 2008, 08:47 AM

Search Tags


/mathhelpforum @mathhelpforum