Results 1 to 3 of 3

Thread: Modular Arithmetic

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    2

    Modular Arithmetic

    Hi,

    Just need help with a couple of Q's.

    Using Euclids algorithm, find:
    3568a = 1 mod 1127

    and

    Use Euclids algorithm to find x and y so 6804x +1343y = 1

    Ty for any help.
    Last edited by Mundaka; Apr 28th 2010 at 12:41 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by Mundaka View Post
    Hi,

    Just need help with a couple of Q's.

    Using Euclids algorithm, find:
    3568a = 1 mod 1127

    and

    Use Euclids algorithm to find x and y so 6804x +1343y = 1

    Ty for any help.

    Read about Bezout's Identity: I'll do (2) and that must suffice to do (1):

    $\displaystyle 6804 = 5\cdot 1343+89$ --- first line

    $\displaystyle 1343=15\cdot 89+8$ --- second line

    $\displaystyle 89=11\cdot 8+1$ --- third line

    $\displaystyle 8=8\cdot 1$ --- fourth and final line

    Now begin from one line before the end upwards, writing each time the remainder as a combination of the other two elements:

    $\displaystyle 1=89-11\cdot 8$ --- from 3rd line

    $\displaystyle 1=89-11\cdot 8=89-11(1343-15\cdot 89)=166\cdot 89-11\cdot 1343$ --- from 2nd line

    $\displaystyle 1=166\cdot 89-11\cdot 1343=166(6804-5\cdot 1343)-11\cdot 1343=166\cdot 6804 -841\cdot 1343$ --- from 1st line

    And voila!: $\displaystyle 1=166\cdot 6804+(-841)\cdot 1343$

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    2
    Thanks.

    That helped me understand it a lot better as well.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 11:07 PM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum