# Chinese Remainder Theorem

Suppose $ax_0+by_0 \equiv ax_1+by_1 \mod ab$. We want to show that $x_0\equiv x_1 \mod b$ and $y_0 \equiv y_1 \mod a$. We have $a(x_0-x_1)+b(y_0-y_1)\equiv 0 \mod ab$. Reducing $\mod a$, we have $a(x_0-x_1)+b(y_0-y_1) \equiv b(y_0-y_1) \equiv 0 \mod a$. Since $(a,b)=1$, this implies $y_0-y_1 \equiv 0 \mod a$. The other part follows similarily.