Maths Olympiad Prep

Library / /518 of 520

Number theory Difficulty 7.9 National olympiad, round 2 Prove it

Theorem 14 Let m=m1m2,(m1,m2)=1m=m_{1} m_{2},\left(m_{1}, m_{2}\right)=1,
x=m2x(1)+m1x(2),x=m_{2} x^{(1)}+m_{1} x^{(2)},

Then, the necessary and sufficient condition for xx to traverse the complete (reduced) residue system modulo mm is that x(1),x(2)x^{(1)}, x^{(2)} simultaneously traverse the complete (reduced) residue systems modulo m1,m2m_{1}, m_{2}, respectively. That is, if
xij=m2xi(1)+m1xj(2)(1is,1jt),x_{i j}=m_{2} x_{i}^{(1)}+m_{1} x_{j}^{(2)} \quad(1 \leqslant i \leqslant s, 1 \leqslant j \leqslant t),

then xij(1is,1jt)x_{i j}(1 \leqslant i \leqslant s, 1 \leqslant j \leqslant t) is a complete (reduced) residue system modulo mm if and only if: xi(1)(1is)x_{i}^{(1)}(1 \leqslant i \leqslant s) is a complete (reduced) residue system modulo m1m_{1} and xj(2)(1jt)x_{j}^{(2)}(1 \leqslant j \leqslant t) is a complete (reduced) residue system modulo m2m_{2}.

Solution

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 s = m_{1}, t = m_{2} . Therefore, there are m1m2 m_{1} m_{2} numbers xij x_{ij} . For any 1i1,i2m1 1 \leqslant i_{1}, i_{2} \leqslant m_{1} , 1j1,j2m2 1 \leqslant j_{1}, j_{2} \leqslant m_{2} , by the condition (m1,m2)=1 \left(m_{1}, m_{2}\right) = 1 and Property IX of §1\S 1, we have:
xi1j1xi2j2(modm) x_{i_{1} j_{1}} \equiv x_{i_{2} j_{2}} (\bmod m)

is equivalent to
xi1j1xi2j2(modm1),xi1j1xi2j2(modm2) x_{i_{1} j_{1}} \equiv x_{i_{2} j_{2}} (\bmod m_{1}), \quad x_{i_{1} j_{1}} \equiv x_{i_{2} j_{2}} (\bmod m_{2})

which is equivalent to
m2xi1(1)m2xi2(1)(modm1),m1xj1(2)m1xj2(2)(modm2) m_{2} x_{i_{1}}^{(1)} \equiv m_{2} x_{i_{2}}^{(1)} (\bmod m_{1}), \quad m_{1} x_{j_{1}}^{(2)} \equiv m_{1} x_{j_{2}}^{(2)} (\bmod m_{2})

By Property V of §1\S 1 and (m1,m2)=1 \left(m_{1}, m_{2}\right) = 1 , this is equivalent to
xi1(1)xi2(1)(modm1),xj1(2)xj2(2)(modm2) x_{i_{1}}^{(1)} \equiv x_{i_{2}}^{(1)} (\bmod m_{1}), \quad x_{j_{1}}^{(2)} \equiv x_{j_{2}}^{(2)} (\bmod m_{2})

Since xi(1),xj(2) x_{i}^{(1)}, x_{j}^{(2)} take values in the same complete residue systems modulo m1 m_{1} and m2 m_{2} respectively, it must be that i1=i2,j1=j2 i_{1} = i_{2}, j_{1} = j_{2} . This proves that these m1m2 m_{1} m_{2} numbers xij x_{ij} are pairwise incongruent modulo m m , i.e., they form a complete residue system modulo m m .

Next, we prove the necessity. Since xij(1is,1jt) x_{ij} (1 \leqslant i \leqslant s, 1 \leqslant j \leqslant t) is a complete residue system modulo m m , we have st=m=m1m2 st = m = m_{1} m_{2} . Fix x1(2) x_{1}^{(2)} , and consider
xi1=m2xi(1)+m1x1(2),1is x_{i1} = m_{2} x_{i}^{(1)} + m_{1} x_{1}^{(2)}, \quad 1 \leqslant i \leqslant s

which are pairwise incongruent modulo m=m1m2 m = m_{1} m_{2} . Therefore, m2xi(1) m_{2} x_{i}^{(1)} are also pairwise incongruent modulo m1m2 m_{1} m_{2} , i.e.,
m2xi1(1)≢m2xi2(1)(modm1m2),1i1i2s m_{2} x_{i_{1}}^{(1)} \not\equiv m_{2} x_{i_{2}}^{(1)} (\bmod m_{1} m_{2}), \quad 1 \leqslant i_{1} \neq i_{2} \leqslant s

This is equivalent to
xi1(1)≢xi2(1)(modm1) x_{i_{1}}^{(1)} \not\equiv x_{i_{2}}^{(1)} (\bmod m_{1})

which means these s s numbers xi(1) x_{i}^{(1)} are pairwise incongruent modulo m1 m_{1} , so sm1 s \leqslant m_{1} . Similarly, we can prove that the t t numbers xj(2) x_{j}^{(2)} are pairwise incongruent modulo m2 m_{2} , so tm2 t \leqslant m_{2} . From st=m1m2 st = m_{1} m_{2} , we conclude s=m1,t=m2 s = m_{1}, t = m_{2} , which proves the necessity.

To prove the conclusion for a reduced residue system, we need to prove (why):
(x,m1m2)=1 \left(x, m_{1} m_{2}\right) = 1

is equivalent to
(x(1),m1)=(x(2),m2)=1 \left(x^{(1)}, m_{1}\right) = \left(x^{(2)}, m_{2}\right) = 1

Since (x,m1m2)=1 \left(x, m_{1} m_{2}\right) = 1 is equivalent to
(m2x(1)+m1x(2),m1)=(m2x(1)+m1x(2),m2)=1 \left(m_{2} x^{(1)} + m_{1} x^{(2)}, m_{1}\right) = \left(m_{2} x^{(1)} + m_{1} x^{(2)}, m_{2}\right) = 1

which is
(m2x(1),m1)=(m1x(2),m2)=1 \left(m_{2} x^{(1)}, m_{1}\right) = \left(m_{1} x^{(2)}, m_{2}\right) = 1

Since (m1,m2)=1 \left(m_{1}, m_{2}\right) = 1 , by Theorem 5 of Chapter 1 §4\S 4, the above is equivalent to equation (19). Proof complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.