1. Limited time only! Sign up for a free 30min personal 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!

Proof of Chinese Remainder Theory

  1. Jun 21, 2014 #1
    1. The problem statement, all variables and given/known data

    Theorm: Let m and n be relatively prime integers. If s and t are arbitrary integers there exists a solution x in Z to the simultaneous congruences:
    x~s (mod m) and x~t (mod n)

    Part of proof that confuses me: Since gcd(m,n) = 1, the Euclidean algorithm gives p and q in Z such that 1 = mp + nq. Take x = (mp)t + (nq)s.

    How do they get the "Take x = (mp)t + (nq)s" part?

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jun 21, 2014 #2
    The Chinese remainder theorem says that a solution exists (or, the part you're trying to prove at least). What he's done is told you the form of the solution to the congruences, and will later show that this is always a solution by virtue of its form, thus proving the theorem.
    Last edited: Jun 21, 2014
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: Proof of Chinese Remainder Theory