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: Diophantine equations

  1. Dec 20, 2004 #1
    ok, so i've never done a problem like this one before:

    find all solutions:

    24x + 11y == 4 (mod 35)
    5x + 7y == -13 (mod 35).

    This reduces to:
    24x + 11y == 4 (mod 5)
    5x + 7y == -13 (mod 5).

    and
    24x + 11y == 4 (mod 7)
    5x + 7y == -13 (mod 7).

    Solving the two, i get (2,1) and (3,4) respectively.
    Do I now apply the CRT to get all the solutions?
     
  2. jcsd
  3. Dec 21, 2004 #2
    I'm not quite sure about it, but I think that you should now solve these systems

    x == 2 (mod5)
    x == 3 (mod7)

    which gives x == 17 (mod35)

    and

    y == 1 (mod5)
    y == 4 (mod7)

    which gives y == 11 (mod35)
     
  4. Dec 21, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, from the above, using CRT gives you :

    [tex]x \equiv 17~(mod~35)~~y \equiv 11~(mod~35) [/tex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook