Proof of Chinese Remainder Theory

[PsychonautQQ]

Homework Statement

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?

Homework Equations

The Attempt at a Solution

 

[1MileCrash]

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.