1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence problem finding smallest modulus.

  1. Apr 1, 2012 #1
    1. The problem statement, all variables and given/known data

    Solve the congruence 20x [itex]\equiv[/itex]16 (mod 92)
    Give your answer to the smallest possible modulus.



    2. Relevant equations



    3. The attempt at a solution

    so 20x -92y=16

    Hence,

    92=20(4) +12.....

    gcd = 4

    working back,

    I have -16(-9)= z (mod 92)

    so z = 52

    and if I divide through by my gcd =4

    36[itex]\equiv[/itex] 13 (mod 23)

    but the answer says -36[itex]\equiv[/itex] 10 (mod 23)

    ??

    Im lost.
     
  2. jcsd
  3. Apr 1, 2012 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Try explaining what you're doing, and do it without so much shorthand.
     
  4. Apr 1, 2012 #3
    Ok, I was being lazy

    Here it is step by step.

    20x[itex]\equiv[/itex]16(mod92)

    so..

    20x - 92y =16

    20 goes into 92, 4 times with 12 remainder


    Hence,

    92 = 20(4) + 12

    12 = 92 - 20(4)

    20= 12(1) + 8

    8= 20 - 12(1)

    12= 8(1) + 4

    4= 12 - 8(1)

    8= 4(2) + 0 [itex]\Rightarrow[/itex] gcd = 4


    working backwards

    4= 12 - (20-12)

    = (92-20(4)) - (20-12)

    = (92-20(4)) - (20-(92-20(4)))

    = 92(2) -9(20)

    so..

    -16(-9) = (?) (mod92)

    144 = 52 (mod92)


    Now dividing through by gcd...

    36[itex]\equiv[/itex] 13 (mod 23)


    But the answer says

    -36[itex]\equiv[/itex]10(mod23)

    I dont understand?
     
  5. Apr 1, 2012 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I was more interested in having you explain what you're doing and why you're doing it, than detailing the individual steps in actually doing it.

    This far, I can determine you intended to find gcd(92,20), along with coefficients u,v satisfying
    gcd(92,20) = 92u + 20v​
    I won't ask why you went off into this calculation, since it's frequently useful enough that it's probably fine to do habitually and without comment.


    However, I can't tell what you were intending to do with the rest of your work:

     
    Last edited: Apr 1, 2012
  6. Apr 1, 2012 #5
    I figured it out I just was shown a bad way with a simpler problem and have been using that approach since.(I was only using one coefficient instead of the two).

    Thanks for the help thoe.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Congruence problem finding smallest modulus.
  1. Congruence problem (Replies: 6)

  2. Finding the modulus (Replies: 2)

Loading...