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!

Homework Help: Solve the congruence to the smallest possible modulus.

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

    solve the congruence to the smallest possible modulus.

    38x[itex]\equiv[/itex]10 (mod84)

    2. Relevant equations

    3. The attempt at a solution

    Ok so I thought I knew how to do these but apparently not.

    So I start out by

    38x+84y = 10

    Now I think I should find the gcd so I can simplify


    84 = 38(2) + 8[itex]\Rightarrow[/itex] 8= 84 - 38(2)

    38= 8(4) + 6 [itex]\Rightarrow[/itex] 6= 38 - 8(4)

    8 = 6(1) + 2 [itex]\Rightarrow[/itex] 2 = 8 - 6(1)

    6 = 2(3) + 0 [itex]\Leftrightarrow[/itex] gcd = 2

    so 19x + 42y = 5

    but then where? I seem to get lost at this point?
  2. jcsd
  3. Apr 2, 2012 #2


    User Avatar
    Science Advisor

    You need to use GCD algorithm, but not just to find GCD. It's a more powerful tool. Let me demonstrate.

    Lets start with your simplified version, 19x=5 (mod42), which you turn into 19x+42y=5. But if you know x, you know y. If you know y, you know x. So we can switch things around.

    42y=5 (mod19)

    Except 42>19, and we can take 19 away twice.

    4y=5 (mod19)

    Better! But why should we stop?


    19z=5 (mod4)

    3z=5 (mod4)


    4w=5 (mod3)


    Woo-hoo! Now, you can use w to find z, z to find y... I'll let you do all that.
  4. Apr 2, 2012 #3
    ok good got it now thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook