Results 1 to 4 of 4

Math Help - Euclidan Algorithm linear congruence

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    6

    Euclidan Algorithm linear congruence

    Use Extended Euclidan Algorithm to find a solution to the linear congruence 16x=11(mod23)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by knights View Post
    Use Extended Euclidan Algorithm to find a solution to the linear congruence 16x=11(mod23)
    The congruence is equivalent to the equation 16x + 23y = 11. Use the extended euclidean algorithm to find integers x' and y' such that 16x' + 23y' = 1. Then multiply by 11 to get x and y.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    3
    Quote Originally Posted by Opalg View Post
    The congruence is equivalent to the equation 16x + 23y = 11. Use the extended euclidean algorithm to find integers x' and y' such that 16x' + 23y' = 1. Then multiply by 11 to get x and y.

    could you work this out for me?

    i'd like to see this also but im still confused
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,697
    Thanks
    1469
    16 divides into 23 once with remainder 7. That is, 1(23)- (1)16= 7. 7 divides into 16 twice with remainder 2: 1(16)- 2(7)= 2. 2 divides into 7 3 times with remainder 1: 1(7)- 3(2)= 1 so 1(7)- 3(16- 2(7))= 7(7)- 3(16)= 1.
    7(23- 16)- 3(16)= 7(23)- 10(16)= 1.

    So one solution to 16x'+ 23y'= 1 is x'= -10, y'= 7. so x= -10(11)= -110 and y= 7(11)= 77 satisfy 16x+ 23y= 11. But that means x= -110+ 23k and y= 77- 16k are solutions for all k because 16(-110+ 23k)+ 23(77- 16k)= -1760+ (16)(23)k+ 1771- (23)(16)k= 1 for all k.

    Now, what values of k make both -110+ 23k and 77- 16k non-negative and less than 23?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 17th 2010, 10:10 PM
  2. Replies: 0
    Last Post: April 13th 2009, 05:53 PM
  3. Euclidan Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2009, 11:18 PM
  4. congruence and the Division Algorithm...
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: July 8th 2008, 07:56 PM
  5. Abstract Algebra: Congruence and The Division Algorithm 1
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 18th 2008, 11:13 AM

Search Tags


/mathhelpforum @mathhelpforum