Chinese Remainder Theorem

**JoAdams5000** · February 25th 2010, 07:33 PM

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!

**Bruno J.** · February 25th 2010, 07:56 PM

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.

Thread: Chinese Remainder Theorem

LinkBack

Thread Tools

Display