Results 1 to 3 of 3

Math Help - Questions on solving linear congruences - Please answer whichever ones you can :)

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    20

    Questions on solving linear congruences - Please answer whichever ones you can :)

    I have to solve the congruence 15x = 45 mod 50. I used the normal equals sign as I can't get the three one.

    To solve it, I did this:

    General linear congruence is ax = b mod n (a,n)=d, where d is the greatest common factor.

    (a,n) = (15,50) = 5 .................. 5 divides 45 => solutions exist.

    15x = 45 mod 50 is the same as 3x = 9 mod 10

    Greatest common factor of (3,10) = 1, and therefore the inverse of 3 exists, which means that x = 3mod 10.


    I don't understand how to get the answer for that very last bit. So what if the inverse exists? Does that mean you simply divide 9 by the number in front of the x? Why not the 10 as well? What if the inverse didn't exist?


    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,423
    Thanks
    1332
    Here is how I would solve such a problem:
    15x= 45 (mod 50). Since both 15 and 45 are divisible by 5, that becomes 3x= 9 (mod 50).

    That means that 3x= 9+ 50y for some integer y. That is the same as 3x- 50y= 9

    Now, 3 divides into 50 16 times with a remainder 2. 2 divides into 3 once with remainder 1.

    That is, 3- 2= 1 and 50- 3(16)= 2. Then 3- (50- 3(16))= 3(17)- 50= 1 and, multiplying by 9, 3(153)- 50(9)= 9. That is, x= 153= 3 (mod 50),

    Check: 15*3= 45 which is, of course, 45 (mod 15).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,690
    Thanks
    617
    Hello, ironz!

    I too have an alternate approach . . .


    15x \:\equiv\:45\text{ (mod 50)}

    We have: . 15x \:=\:50a + 45

    Solve for x\!:\;\;3x \:=\:10a + 9 \quad\Rightarrow\quad x \:=\:\dfrac{10a+9}{3}

    And we have: . x \:=\:3a + 3 + \dfrac{a}{3} .[1]


    Since \,x is an integer, \,a must be a multiple of 3: . a \,=\,3b

    Substitute into [1]: . x \:=\:3(3b) + 3 + \dfrac{3b}{3} \quad\Rightarrow\quad x\;=\;10b + 3


    Therefore: . x \:\equiv\:3,\,13,\,23,\,33,\,43 \text{ (mod 50)}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 02:07 AM
  2. Trouble solving a system of linear congruences.
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 14th 2010, 10:10 AM
  3. Solving linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 12th 2010, 10:46 PM
  4. Solving Congruences
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: August 5th 2009, 10:34 PM
  5. Solving congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 31st 2009, 11:16 PM

Search Tags


/mathhelpforum @mathhelpforum