Results 1 to 2 of 2

Thread: Solve the equation 3x ≡ 5 (mod 22) using the extended Euclidean Algorithm.

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Solve the equation 3x ≡ 5 (mod 22) using the extended Euclidean Algorithm.

    This one ..well I hope it's ok ..bit rusty on the mods.
    To find the reciprocal of 3 (mod 22) we must first ensure it exists by finding if they have 1 as their greatest common factor(thanks HallofIvy) remembered to put this
    gcd(22,3): 22 = 7 ⋅ 3 + 1 1 = 22 ⋅ 1 3 ⋅ 7
    -7 ⋅ 3 ≡ 1 (mod 22)

    3x ≡ 5 (mod 22)
    -7 ⋅ 3x ≡ -7 ⋅ 5 (mod 22)[multiply both sides by -7]
    1x ≡ -35 (mod 22) [sub in 7 ⋅ 3 ≡ 1 (mod 22)]
    x ≡ -13 (mod 22) [add 22 to -35]
    x ≡ 9 (mod 22)[add 22 to -13]

    Which Im pretty sure works because 5 mod 22 ≡ {...,-39,-17,5,27,49,71, ...}
    So you just find one that 3 goes into (27) to get 3x9 ≡ 5 mod 22, so x ≡ 9 (mod 22)

    Is this ok??

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,337
    Thanks
    2859

    Re: Solve the equation 3x ≡ 5 (mod 22) using the extended Euclidean Algorithm.

    Yes, that is ok. And it is easy to check that 3(9)= 27= 22+ 5= 5 (mod 22).
    Frankly, I wouldn't have bothered to check on the "gcd" since if there is no solution, that will appear while trying to solve.

    Here is how I would solve "3x= 5 (mod 22)". That is the same as 3x- 22y= 5 for integers x and y. Now, 3 divides into 22 7 times with remainder 1: 22- 3(7)= 1. So one solution to "3x- 22y= 1" is x= -7, y= -1. From that, one solution of "3x- 22y= 5" is x= -7(5)= -35= - 44+ 9= 9 (mod 22) and y= -1(5)= -1= -22+ 21= 21 (mod 22).

    So the solution to the problem is x= 9 (mod 22).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: Mar 5th 2013, 03:03 PM
  2. Extended Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2011, 07:27 AM
  3. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Dec 11th 2010, 05:25 AM
  4. Extended Euclidean algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 21st 2009, 01:24 PM
  5. Replies: 6
    Last Post: Mar 31st 2009, 05:44 PM

/mathhelpforum @mathhelpforum