Results 1 to 3 of 3

Math Help - linear congruence by euclidean algorithm

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    pepperland
    Posts
    2

    linear congruence by euclidean algorithm

    Hey!

    I have a question about solutions of linear congruences with Euclidean algorithm. I'd be very happy if you can help.

    9x=1 (mod 16)
    What I know is gcd of 9 and 16 is equal to 1 and it divides 1. Thus exists a unique solution.
    But I cannot figure out how to find x=9 by Euclidean way.

    If someone helps or just tries, thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,706
    Thanks
    625

    Re: linear congruence by euclidean algorithm

    Hello, jethrotulL!

    Even if you don't know (or understand) the Euclidean algorithm,
    . . you can still solve it.


    Solve by the Euclidean algorithm: . 9x\:\equiv\:1\text{ (mod 16) }

    We have: . 9x \:=\:16a + 1\,\text{ for some integer }a.

    Solve for x\!:\;x \:=\:\frac{16a+1}{9} \:=\:a + \frac{7a+1}{9} .[1]

    Since x is an integer, 7a+1 must be a multiple of 9.
    . . That is: . 7a+1 \:=\:9b\,\text{ for some integer }b.

    Solve for a\!:\;a \:=\:\frac{9b-1}{7} \:=\:b + \frac{2b-1}{7} .[2]

    Since a is an integer, 2b-1 must be a multiple of 7.
    . . The first time this happens is b = 4

    Substitute into [2]: . a \:=\:4 + \frac{2(4)-1}{7} \quad\Rightarrow\quad a\,=\,5

    Substitute into [1]: . x \:=\:5 + \frac{7(5)+1}{9} \quad\Rightarrow\quad \boxed{x \,=\,9}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    pepperland
    Posts
    2

    Re: linear congruence by euclidean algorithm

    Thank you, but I need to solve it by euclidean algorithm. Can you also solve by this way please?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: April 13th 2009, 05:53 PM
  2. Euclidan Algorithm linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 9th 2009, 11:35 AM
  3. Euclidean Algorithm - Linear Combination
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 26th 2008, 12:04 PM
  4. congruence EQ using Euclidean!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 25th 2007, 05:13 AM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum