1. Not finding help here? Sign up for a free 30min 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!

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

Have something to add?