Results 1 to 2 of 2
Like Tree2Thanks
  • 2 Post By HallsofIvy

Math Help - How do you solve linear congruences?

  1. #1
    Newbie
    Joined
    Feb 2014
    From
    United States
    Posts
    21

    How do you solve linear congruences?

    Hi all,

    So we just covered solving congruence's in my discrete 1 class. Our professor gave us 1 example in the notes, and to be honest it sucked and I don't understand it at all. Can someone explain to me how you solve this linear congruence(the one example she did in class)

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,536
    Thanks
    1391

    Re: How do you solve linear congruences?

    Can we assume that you know what "congruent modulo 27" means? Two numbers, x and y, are "congruent modulo 27" if and only if there difference, x- y, is a multiple of 27. Equivalently, if they have the same remainder when divided by 27.

    Here, the problem is to find x such that 10x= 2 (mod 27). That is the same as saying that 10x= 27k+ 2 and that is the same as the "Linear Diophantine" equation 10x- 27k= 2.

    10 divides into 27 twice with remainder 7: 27- 2(10)= 7.
    7 divides into 10 once with remander 2: 10- 7= 3.
    3 divides into 7 twice with remainder 1: 7- 2(3)= 1

    Replace the "3" in that last equation with 10- 7: 7- 2(10- 7)= 3(7)- 2(10)= 1.

    Replace the "7" in that equation with 27- 2(10): 3(27- 2(10))- 2(10)= 3(27)- 8(10)= 1.

    Multiply through by 2: 6(27)- 16(10)= 2.

    So one solution is x= -16, k= -6. But adding any multiple of 27 to x and any multiple of 10 to k is also a solution:
    10(-16+ 27n)- 27(-6+ 10n)= -160+ 270n-(-162+ 270n)= 2 for any integer n:
    x= -16+ 27n, k= -6+ 10n. In particular, taking n= 1 gives x= -16+ 27= 11, the only solution lying between 0 and 27.

    As a check, 10(11)= 110= 4(27)+ 2.
    Thanks from michaelgg13 and macosxnerd101
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. solve congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 8th 2013, 04:19 PM
  2. [SOLVED] Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 26th 2011, 09:28 PM
  3. Cant solve these... Congruences !!
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 4th 2010, 07:57 AM
  4. solve congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 17th 2009, 10:00 PM
  5. solve quadratic congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 12th 2008, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum