Proof: First, it should be pointed out that the form of Theorem 14 is different from the previous theorems; the condition here is both sufficient and necessary, making the conclusion stronger. We will first prove it for a complete residue system. We start by proving the sufficiency (which can be derived using Theorem 11 and Theorem 10, but we will provide a direct proof here). At this point, s=m1,t=m2. Therefore, there are m1m2 numbers xij. For any 1⩽i1,i2⩽m1, 1⩽j1,j2⩽m2, by the condition (m1,m2)=1 and Property IX of §1, we have:
xi1j1≡xi2j2(modm)
is equivalent to
xi1j1≡xi2j2(modm1),xi1j1≡xi2j2(modm2)
which is equivalent to
m2xi1(1)≡m2xi2(1)(modm1),m1xj1(2)≡m1xj2(2)(modm2)
By Property V of §1 and (m1,m2)=1, this is equivalent to
xi1(1)≡xi2(1)(modm1),xj1(2)≡xj2(2)(modm2)
Since xi(1),xj(2) take values in the same complete residue systems modulo m1 and m2 respectively, it must be that i1=i2,j1=j2. This proves that these m1m2 numbers xij are pairwise incongruent modulo m, i.e., they form a complete residue system modulo m.
Next, we prove the necessity. Since xij(1⩽i⩽s,1⩽j⩽t) is a complete residue system modulo m, we have st=m=m1m2. Fix x1(2), and consider
xi1=m2xi(1)+m1x1(2),1⩽i⩽s
which are pairwise incongruent modulo m=m1m2. Therefore, m2xi(1) are also pairwise incongruent modulo m1m2, i.e.,
m2xi1(1)≡m2xi2(1)(modm1m2),1⩽i1=i2⩽s
This is equivalent to
xi1(1)≡xi2(1)(modm1)
which means these s numbers xi(1) are pairwise incongruent modulo m1, so s⩽m1. Similarly, we can prove that the t numbers xj(2) are pairwise incongruent modulo m2, so t⩽m2. From st=m1m2, we conclude s=m1,t=m2, which proves the necessity.
To prove the conclusion for a reduced residue system, we need to prove (why):
(x,m1m2)=1
is equivalent to
(x(1),m1)=(x(2),m2)=1
Since (x,m1m2)=1 is equivalent to
(m2x(1)+m1x(2),m1)=(m2x(1)+m1x(2),m2)=1
which is
(m2x(1),m1)=(m1x(2),m2)=1
Since (m1,m2)=1, by Theorem 5 of Chapter 1 §4, the above is equivalent to equation (19). Proof complete.