For the proof, let p and q be coprime

Rearrangement

x = a m o d p x = b m o d q

Subtract a from both equations

x - a = 0 m o d p x - a = b - a m o d q

The Underlying Problem

Let m be an integer from 0 to q-1 (inclusive), and r be an integer from 0 to q-1 (inclusive)

m p = r m o d q

There are q possible values of m, and q possible values of r.

Since p and q are coprime, the remainders cannot repeat until after m > q-1

Therefore, there is a unique value of m to produce any remainder r in the above equation.

Putting it all Together

If we look at the last equation in Rearrangement, we see it matches the equation in The Underlying Problem, where b-a corresponds to r, and x-a corresponds to mp.

So, we can see there is one unique solution for x in the interval of 0 to pq-1 (inclusive)

We can extend this by saying there will be a solution pq larger than another solution, making the solutions expressible via mod.

The Underlying Problem (but rigour)

Again start with

m p \equiv r mod q

Suppose $m_{1}$ and $m_{2}$ are two $m$ that give the same $r$ . Then $p m_{1} \equiv p m_{2} mod q$ . By the cancellation law $m_{1} \equiv m_{2} mod q$ , since $g cd (p, q) = 1$ .

Cancellation Law Proof (Brownie Points)

p m_{1} - p m_{2} = p (m_{1} - m_{2})

Know $q$ divides $p m_{1} - p m_{2}$ since they are both the same mod $q$ , therefore $q$ divides the RHS. By Euclid’s Lemma $q$ must divide $m_{1} - m_{2}$ , meaning $m_{1} \equiv m_{2} mod q$ .

Final Theorem

Let p and q be coprime. If:

then:

x re m pq

exists and is unique.

Notes

x = 0 m o d y x re m y = 0

both mean x is divisible by y.

x = a m o d p x = b m o d q

@craisin's notes

Explorer

Chinese Remainder Theorem (+ Cancellation Law Proof)