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. Dec 6, 2008 #1
    Hi,

    I can not see how this is implied...

    Let m and n be positive integers, with gcd(m, n) = 1. The the system of congruences

    x = a (mod m) and x = b (mod n ) has a solution. Moreover, any two solutions are congruent modulo mn.

    pf.

    Since gcd(m,n) = 1, there exist integers r and s such that rm + sn = 1. Then rm=1 mod n and sn = 1 mod m. And the proof goes on.

    I just do not understand how "Then rm=1 mod n and sn = 1 mod m." is true.

    Can anyone clarify. Thanks
     
  2. jcsd
  3. Dec 6, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, the previous step in the proof was to get the equation
    rm + sn = 1,​
    (and some of those variables didn't appear beforehand) so I bet that's important....
     
  4. Dec 6, 2008 #3
    ... I'm not sure what your getting at but I think your question is why is

    rm + sn = 1

    true

    and it follows from the Euclidean algorithm, which I understand.
     
    Last edited: Dec 6, 2008
  5. Dec 6, 2008 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, what do you know about modular arithmetic?
     
  6. Dec 6, 2008 #5
    I have some exposure to modular arithmetic, I should know this and understand it clearly but, I have been struggling with it for a while now.

    I understand that if x = a (mod n) and x = b (mod m) with gcd(n,m) = 1

    they we can find x if we can find integers y and z such that

    y = 1 (mod n) and y = 0 (mod m)
    and
    z = 0 (mod n) and z = 1 (mod m)

    with x = ya + zb

    because

    ya + zb = 1a + 0b = a (mod n)
    and
    ya + zb = 0a + 1b = b (mod m)
     
  7. Dec 7, 2008 #6
    If you have an initial equation rm + sn = 1, and you want to arrive to rm = 1 (mod n), what can you notice in the initial equation regarding divisibility by n?
     
  8. Dec 7, 2008 #7

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    here is a less constructive proof. you want to show the map Z--Z/n x Z/m is surjective.

    first find the kernel. i.e. which x in Z go to zero in both Z/n and Z/m? such x are divisible by both n and m so are divisible by the product nm (why?).

    thus the induced map Z/nm --> Z/n x Z/m is injective since we have set the things that go to zero, themselves equal to zero. but now we have an injective map betwe two sets of the same cardinality, hence it must be surjective.
     
  9. Dec 7, 2008 #8
    I notice that n|sn --> sn is congruent to 0 mod n
    and rm is congruent to 1 mod n iff rm = 4n + 3 for q an integer, by the division theorem.

    but I still am not really seeing anything from this...

    This is a little too funny, this is almost what I am trying to prove. It is nice because I think I am on the right track, maybe I should take a different approach.

    I am trying to show ZmnX is isomorphic to ZmXXZnX given that the gcd(m,n) is 1.

    I will post my work soon.
     
    Last edited: Dec 7, 2008
  10. Dec 7, 2008 #9
    I want to find an isomorphism between the groups as described above.
    So, I want f to be bijective and to also satisfy, for [a]mn, mn elements of ZmnX,

    I want to show this --> direction, (doest the other way look easier or clearer)

    f([a]mnmn) = f([a]mn)f(mn)

    ... I really don't know how to construct f, I have no idea how to create a bijection even going the other way

    for elements [a]m, n of ZmX and ZnX respectively construct a bijection such that

    f([a]mn) = f([a]m)f(n)

    but the elements look like [a]mn--->([ab]mn)

    I have the ker(f) = {([1]m,[1]n)} or {[1]mn} depending on the way I end up going.

    I know that Eulers totient function, phi, gives phi(mn)=phi(m)phi(n). All that really gives is equal cardinality though.

    WLOG I can claim m>=n.

    So, I think I want,

    f: [a]mn to ([a]m,[a]n).

    So then we have

    f([a]mnmn) = f([a]mn)f(mn)

    LHS gives
    f([a]mnmn) = f([ab]mn) = ([ab]n,[ab]n)

    and the RHS gives
    f([a]mn)f(mn) = ([a]m,[a]n)(m,n) = ([ab]n,[ab]n)

    So the LHS = RHS and that shows this is a homomorphism,

    Now for the bijection, using the ker(f) gives the trivial solution this is injective, and with the totient function give that the cardinality is equal, f must also be surjective.

    So, does this look right?
     
  11. Dec 18, 2008 #10

    If I understand well, if is VERY EASY! So easy that it could be even confusing.

    Definition say that [tex]a \cong b[/tex] mod [tex] n [/tex] IF and ONLY IF [tex] n [/tex] divides [tex] b-a [/tex]. Is that right???
    So if you have
    [tex] rm + sn = 1 [/tex]
    then you have
    [tex]sn - 1 = rm[/tex] and [tex] m [/tex] divides obviously [tex] rm [/tex]. So you get that [tex] m [/tex] divides [tex] sn- 1 [/tex] and this is by definition equivalent to say that [tex] sn \cong 1 [/tex] mod [tex] m [/tex].

    The next result is similar. [tex]rm + sn = 1[/tex] means [tex]rm -1 = sn[/tex] so [tex] n [/tex] divides [tex]rm - 1[/tex] and you get
    [tex]rm \cong 1[/tex] mod [tex] n [/tex].


    Was this the thing you couldn't get????? Or there is something more????
     
    Last edited: Dec 18, 2008
  12. Dec 18, 2008 #11
    Can't understand why the TeX writings don't quite work good so I rewrite everuthing in normal text mode.


    If I understand well, if is VERY EASY! So easy that it could be even confusing.

    Definition say that a = b mod n IF and ONLY IF n divides b-a. Is that right???
    So if you have

    rm + sn = 1

    then you have

    sn - 1 = rm

    and m divides obviously rm.

    So you get that m divides sn - 1 and this is by definition equivalent to say that

    sn = 1 mod m.



    The next result is similar.

    rm + sn = 1

    means

    rm -1 = sn

    so n divides rm - 1 and you get

    rm = 1 mod n.


    Was this the thing you couldn't get????? Or there is something more????
     
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...