Results 1 to 6 of 6

Math Help - linear congruences

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    22

    linear congruences

    Q1.find an inverse of 19modulo 43.

    so far I have worked through euclids algorithm to find gcd(19,43)=1. however when I try to work the algorithm in reverse to solve 19x +43y=1 I get confused.

    Q2. Solve 19x congruend to 17 mod 43.

    I assume this will be easier to answer once I have the answer for q1?! I have attempted to solve this by trying to solve 19x-43t=17, again I have worked through euclids algorithm to find again that gcd(19,43)=1, however once again I get confused when trying to work the algorithm in reverse.

    Q3. Solve the system 19x congruent to 17 mod 43 and
    x congruent to 18 mod 19.

    Again I assume this will be easier once I have solved q1 and 2.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396

    Hi

    Q2:

     19x \equiv 17 (mod 43)

    This means:  19x - 43k = 17

    Solve this diofanthine equation by first constructing the help equation, HE.

    HE:  19x - 43k = 1

    You say you know Euclides Algorithm. Working it backwards can be tricky, and obv the correctnes of the solution depends on not making any mistakes here.

     1 = 5 - 1*4 \ = 5 -1*(19 - 3*5)  = 43 -2*19 -1*(19 - 3*(43 - 2*19))  = 43 - 2*19 - 1*19 + 3*43 - 6*19 \ = -9*19 + (-43)*(-4)

    So we end up with a solution to HE being  x = -9  \ \mbox{and}\ k = -4

    Now multiply both the x-solution and k-solution with 17.
    So you get ONE solution for  19x - 43k = 17

    This solution is:  x = -153 \ \mbox{and} \ k = -68

    Now we write:  x = -153 + 43*n \ \mbox{for some integer n}

    Since we are often interested in the positive solutions we get  x = 19

    Q3. Try doing the same with Q3, and then you have to find an x satisfying both these equations.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    22
    please could you explain a couple of steps for me...

    the first is how we got 43- 2x19 + 43 - 6x19 = -9 x 19 + (-43)x(-4)

    and then how from x=-153 and k=-68 we produce x=-153+43n resulting in x=19?!

    i have followed everything else you said thank you.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396

    hi again

    Hi!

    When using Euclides algorithm backwards, you want to express the number 1, in terms of (in this particular case) 43 and 19.

    So we "go backwards" by substituting (first step) 4 with  19 - 3*5

    Now it is important that YOU DO NOT write  3*5 as  15

    In the next step you replace 5 with  43 - 2*19

    Then it is simply a matter of simplifying the expression.
    And we end up with  -9 * 19 \ \mbox{and} \ (-43)*(-4)

    If you test this solution then this should come out to be just 1, which was our goal in the first place.
    Then to make this a solution for  19x - 43k = 17 , you need to multiply your solution with 17.

    We are only interested in the x in this equation, and we prefer positive values on x.

    So we can write  x = -153 + 43*n \ \mbox{for some integer n, in this case n=4}

    By doing so we can increase our x-value by multiples of 43.
    And the lowest positive value for x is just  x = 19

    Iīm not great at explaining this, esp. since I am very new at this myself...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2008
    Posts
    22
    No thats brilliant, thank you very much. Sorry to ask for further explanation I just want to ensure I have a full understanding should I be faced with another problem with different values.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Twig's Avatar
    Joined
    Mar 2008
    From
    Gothenburg
    Posts
    396
    No problemo.

    And I agree, if one doesnīt learn how to solve different equations and fully understand the concept, then itīs pointless.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 26th 2011, 10:28 PM
  2. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 03:07 AM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 19th 2009, 09:02 PM
  4. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 19th 2009, 10:33 PM
  5. linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2008, 09:27 PM

Search Tags


/mathhelpforum @mathhelpforum