Chinese Remainder Theory

02172010, 03:09 PM
(This post was last modified: 11222014 10:38 PM by elim.)
Post: #1




Chinese Remainder Theory
The theorem statement: \(\left((n_i,n_j)=1, \quad 1<=j<j<=k \right) \Rightarrow \)
\[\forall (a_1,\cdots,a_k) \in \mathbf{N}_0^k \quad \exists x_0 \in \mathbf{N}_0 \left(x_0 \equiv a_i (\textrm{mod} \; n_i) \quad i=\overline{1,k}\right) \wedge \]\[\left( (x \equiv a_i (\textrm{mod} \; n_i) \quad i=\overline{1,k}) \Leftrightarrow ( x \equiv x_0 (\textrm{mod} \; n_1 \cdots \; n_k))\right) \] Proof. Let \(N = \prod_{i=1}^k n_i\) then \((n_i, N/n_i)=1\) hence \(\exists s_i,t_i \in \mathbf{Z}: \quad s_i n_i + t_i (N/n_i) = 1 \quad i=\overline{1,k}\). Let \(e_i = t_i (N/n_i)\), then \(\left( e_i \equiv 0 (\textrm{mod}\; n_j) \quad i \neq j\right) \wedge \left( e_i \equiv 1 (\textrm{mod}\; n_i)\right)\). So \(x_0 = \sum_{i=1}^k a_i e_i\) satisfies \(x_0 \equiv a_i (\textrm{mod}\; n_i) \quad i=\overline{1,k}\). Now \(\left( x\equiv a_i (\textrm{mod}\; n_i) \quad i=\overline{1,k}\right) \Leftrightarrow \left( xx_0 \equiv 0 (\textrm{mod}\; n_i), \quad i=\overline{1,k}\right) \Leftrightarrow \left( x\equiv x_0 (\textrm{mod}\;N)\right)\) Q.E.D As an example, we look at HanXing's Soldier Counting (韩信点兵) 三人同行七十稀，五树梅花廿一枝， 七子团圆正半月，除百零五便得知。 The Chinese above is a mystery poemcode of (**) below: (**) \(x \equiv 70[x]_3+21[x]_5+15[x]_7 (\textrm{mod}\; 105) \quad \quad \quad (105 = 3\times 5\times7)\) Where \([x]_j = \textrm{min} \left\{m \in \mathbf{N}_0: j(xm)\right \}\) is the remainder of \(x\) by \(j\). The poem, in English sounds roughly like this to me: Rarely you see 3 men walking together all above 70's, But 5 and 21 surely show the beauty of plum blossoms, 7 sons' reunion expects full moon at middle month sky, with these to a multiple of 105 you figure it out all! Note: In Chinese lunar calendar, full moon always appears at the middle of the month. which implies number 15. Let's say from 3 friends you get their age's remainders of 3,5 and 7 respectively (instead of the age themselves) as(for some \(n \in \mathbf{Z}\)): (1) \(0,1,1\). Then \(70 \times 0+ 21 \times 1 + 15 \times 1 = 36\) hence the number in mind is \(36 + 105n\) (2) \(1,4,0\). Then \(70 \times 1 + 21 \times 4 + 15 \times 0 = 154\) hence the number in mind is \(49 + 105n\) (3) \(1,3,4\). Then \(70 \times 1 + 21 \times 3 + 15 \times 4 = 193\) hence the number in mind is \(88 + 105n\) You see that you can actually get their real ages! Below is some more general arguments. If we know the number's range is \([k, k+105)\) for some \(k \in \mathbf{Z}\), we then get the definite answer. So if you ask people choose a number from \([1,100]\) and let them to provide the remainders with respect to 3,5 and 7, you know exactly what in their mind. This is quite amazing for most people. But in US, figure out remainders is already too hard... That's why we are good at complicated measure systems: Let computer figure things out. 

« Next Oldest  Next Newest »
