1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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 Threads - Proof Chinese Remainder Date
Lim sup proof Mar 12, 2018
Real Analysis Proof Mar 11, 2018
Chinese Remainder theorem for 2 congruences Mar 10, 2018
Proof that a recursive sequence converges Mar 8, 2018
Bland rule proof linear programming Mar 7, 2018