# Math Help - Chinese Remainder Theorem

1. ## Chinese Remainder Theorem

Suppose (a,b) = 1. As x runs through a complete residue system (mod b) and y runs through a complete residue system (mod a), then ax + by runs through a complete residue system (mod ab).

I'm curious as to whether this is true. I've tried many examples but have failed to prove the above statement. Any help would be great. Thanks!

2. 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.