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!

Chinese Remainder Theorem

  1. Nov 5, 2008 #1
    This doesn't actually require the use of the CRT, since it actually wants you to sort of derive it for a system of two equations. So while using the CRT will help me solve this fairly quickly and easily, that's not what I'm after

    1. The problem statement, all variables and given/known data
    Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that
    [tex]c\equiva(mod m)[/tex] and [tex]c\equivb(mod n)[/tex]

    2. The attempt at a solution

    now, sm + tn = 1 for some integers s,t. It's obvious that
    [tex]sm\equiv0(mod m)[/tex] and [tex]tn\equiv0(mod n)[/tex]

    I know I'm suppose to use sm and tn as coefficients to combine a and b, but I'm not really sure how to go about it. I've tried adding tn to get 1 == tn (mod m) but I'm not sure that's correct. And even if it is, I multiply by a or by b and can still not figure it out. I end up in circles and get c == a (mod m). -_- Can you lend me hand? Remember, don't give me the chinese remainder theorem, because that's not what the excercise is about.
     
  2. jcsd
  3. Nov 5, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's essentially a linear algebra problem -- your "vectors" are the two-tuples whose components are "value mod m" and "value mod n", and you seek to express a particular vector as an integer linear combination of the two vectors you have already considered.


    Well, have you thought about how you might prove it? If not, can you explain why you think it might be true?
     
  4. Nov 5, 2008 #3

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Do you mean that you are trying to show that you can always find integer [itex]c[/itex] such that:

    [tex]c \equiv a \quad (\text{mod} \; m)[/tex] and [tex]c \equiv b \quad (\text{mod} \; n)[/tex]

    ?
     
  5. Nov 5, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that [itex]c (mod m)[/itex] and [itex]c (mod n)[/itex]" makes no sense. What is supposed to be true of [itex] c (mod m)[/itex] and [itex]c (mod m)[/itex]? That they are equal?
     
  6. Nov 5, 2008 #5
    yes, gabbagabbahey, sorry that's what I meant:
    [tex]c \equiv a \quad (\text{mod} \; m)[/tex]
    [tex]c \equiv b \quad (\text{mod} \; n)[/tex]

    So since [tex]sm \equiv 0 (\text{mod} \; m)[/tex] then, I thought
    [tex]tn + sm \equiv tn (\text{mod} \; m)[/tex]
    [tex]1 \equiv tn (\text{mod} \; m)[/tex]
     
  7. Nov 5, 2008 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, this is definitely correct.
     
  8. Nov 5, 2008 #7
    hmm, looking at it though, I don't think it would get me anywhere would it? Rather, the congruence also implies

    [tex]tn \equiv 1 (\text{mod} \; m)[/tex] therefore
    [tex]atn \equiv a (\text{mod} \; m)[/tex]
    and in the same way you can get

    [tex]bsm \equiv b (\text{mod} \; n)[/tex]

    then, can you say bsm + atn is congruent to both a (mod m) and b (mod n); hence that's the c I'm looking for?
     
  9. Nov 5, 2008 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You seem hesitant to assert that -- what might be a problem? If you can indeed prove both of those congruences, it sounds like you've constructively shown the existence of such a c.
     
  10. Nov 5, 2008 #9
    I guess I'm convinced; after all if you have
    bsm + atn == a (mod m)
    0 + atn == a (mod m)
    and we've seen tn == 1 (mod m), so
    a == a (mod m); similarly for bsm == b (mod n)

    If I can ask another question;
    What if gcd(m,n)=k for some k>1
    Going through similar steps I obtain
    [tex]atn \equiv ak (\text{mod} \; m)[/tex]

    I thought, you would need to obtain the inverse of k modulo m (assuming m is prime, and therefore the inverse exists). Let f be the inverse of k (mod m). Then
    [tex]fatn \equiv fak (\text{mod} \; m)[/tex]
    [tex]fatn \equiv a (\text{mod} \; m)[/tex]

    Similarly for bsm, you would obtain
    [tex]bsm \equiv bk (\text{mod} \; n)[/tex]
    [tex]gbsm \equiv gbk (\text{mod} \; n)[/tex] where g is the inverse of k (mod n)
    [tex]gbsm \equiv b (\text{mod} \; n)[/tex]

    Therefore our c = fatn + gbsm. Correct?
    If either m or n, possibly both, are not prime, then you would you still have a solution for this only if the inverse of k exists for both (mod m) and (mod n). If it doesn't, then is the system not solvable?
     
  11. Nov 5, 2008 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I believe you know exactly when k, as defined, is invertible modulo m....

    I believe it might be better to first work through the case where you have many different relatively prime moduli. Once you understand that, you can then reduce to it the case where you have two moduli that are not relatively prime.

    Alternatively, you might first try to work out exactly when a single linear modular equation does and does not have a solution (and if it does, how many).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Chinese Remainder Theorem
Loading...