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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Solve the congruence to the smallest possible modulus.
  1. Solving a congruence (Replies: 2)