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!

Solving simultaneous congruences

  1. Oct 4, 2015 #1
    1. The problem statement, all variables and given/known data

    Find all integers ##n## which satisfies ##n\equiv_7 13## and ##n \equiv_5 2##

    2. Relevant equations
    -

    3. The attempt at a solution

    I get that ##n\equiv_7 13## is the same thing as ##n\equiv_7 -1## and more generally ##n={-1}+7x##, {##x\cup \mathbb{Z}##} for any multiple of 7.

    The other congruence could be written as ##n=2+5y##, {##y\cup \mathbb{Z}##}.

    I can input different integers for ##x## and ##y## and by doing that I can see that ##27## solves both congruences. Since ##5## and ##7## is relative prime the solution should be ##n=27+(5*7)## and more generally ##n=27+(5*7)z##, {##z\cup \mathbb{Z}##}.

    But I believe this is just a cheap way of finding the solution. How can one go about to make a better solution? It would prolly involve diophantine equations? It feels like I just got lucky this time. Anyone got a tips on how to attack these types of problems in a better way? Thanks
     
  2. jcsd
  3. Oct 4, 2015 #2

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    You may want to look into the Chinese remainder theorem.
     
  4. Oct 4, 2015 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    n= 13 (mod 7) is the same as n= 6 (mod 7) or n= 6+ 7k for some integer k. Similarly, n= 2 (mod 5) is the same as n= 2+ 5i for some integer i. Then 6+ 7k= 2+ 5i which gives 5i- 7k= 4, a Diophantine equation.
     
  5. Oct 5, 2015 #4
    Oh, of course! So when I use Euclid's algorithm I end up with ##7=1*5+2## and ##5=2*2+1##. How can I make any sense of this in my case? I've seen examples where you do the extended Euclid's algorithm and you get all these terms which you substitute to end up with something that solves the linear relation but I only get two lines with a remainder ##\neq0##.
     
  6. Oct 5, 2015 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I would write those as 7- 5= 2 and 5- 2(2)= 1. So 5- 2(7- 5)= 3(5)- 2(7)= 1. Can you finish that? What do you need to do to get "= 4"?
     
  7. Oct 5, 2015 #6
    Thanks HallsofIvy. Right! So I just multiply both sides by 4 (and keep the coefficiants unchanged) and end up with ##12(5)-8(7)=4##. So all the solutions for the variables as you named them ##i## and ##k## would be ##i=12-8*m## and ##k=(-8)+12*m##, {m∪ℤ}, right?

    But how do I get from this to finding n via this method?
     
  8. Oct 6, 2015 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The initial problem was to find n such that n= 13 (mod 7)= 6 (mod 7) which is the same as n= 6+ 7k for some k, and n= 2 (mod 5) which is the same as n= 2+ 5i for some integer i. That led to the Diophantine equation 5i- 7k= 4. You are correct that 12(5)- 8(7)= 4 but from that point you have several errors: i= 12 and k= 8 (NOT -8) satisfy the equation, the "-" was already in the equation. Also if we add any multiple of the coefficient, 5 (NOT the solution, 12), to k, k= 8+ 5m, and any multiple of the coefficient, 7, (NOT the solution, 8) to i, i= 12+ 7m will satisfy that equation: 5(12+ 7m)- 7(8+ 5m)= 60+ 35m- 56- 35m= 4 for all m.

    The original problem was to find n such that n= 13= 6 (mod 7) and n= 2 (mod 5). The first is the same as saying n= 6+ 7k and the second is the same as n= 2+ 5i for integers k and i. Now that we have found that k= 8+ 5m and i= 12+ 7m, we can find n: if k= 8+ 5m then n= 6+ 7(8+ 5m)= 6+ 56+ 35m= 62+ 35m for any integer, m. If i= 12+ 7m, then n= 2+ 5(12+ 7m)= 2+ 60+ 35m= 62+ 35m for any integer m. Use that to find n in terms of the general integer, m.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Solving simultaneous congruences
  1. Solving a congruence (Replies: 2)

Loading...