Results 1 to 3 of 3

Math Help - 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; April 28th 2010 at 12:41 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    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):

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

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

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

    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:

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

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

    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!: 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: March 28th 2010, 05:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum