MATH 361: NUMBER THEORY — FIFTH LECTURE1. The Sun Ze TheoremThe Sun Ze Theorem is often called the Chinese Remainder Theorem. Here isan example to motivate it. Suppose that we want to solve the equation13x = 23 mod 2310.(Note that 2310 = 2 · 3 · 5 · 7 · 11.) Since gcd(13, 2310) = 1, we can solve thecongruence using the extended Euclidean algorithm, but we want to think about itin a different way now. The idea is that13x = 23 mod 2310⇐⇒13x = 23 (2), 13x = 23 (3), 13x = 23 (5), 13x = 23 (7), 13x = 23 (11)⇐⇒x = 1 (2), x = 2 (3), 3x = 3 (5), 6x = 2 (7), 2x = 1 (11)⇐⇒x = 1 (2), x = 2 (3), x = 1 (5), x = 5 (7), x = 6 (11).The process has reduced one linear congruence with a large modulus to a systemof linear congruences with smaller moduli. Furthermore, the moduli are pairwisecoprime.In general, given pairwise coprime positive integers n1, . . . , nk, compute theintegersei=Yj6=inj×Yj6=inj−1mod ni, i = 1, . . . , k.These numbers satisfy the conditionsei=(1 mod ni0 mod njfor j 6= i.That is, they are rather like the standard basis of Rnin that each eilies one unitalong the ith direction and is orthogonal to the other directions. But in this context,direction refers to a modulus.With the eiin hand, we can solve the system of congruencesx = a1(n1), x = a2(n2), · · · , x = ak(nk).A solution is simply the obvious linear combination,x = a1e1+ a2e2+ · · · + akek.12 MATH 361: NUMBER THEORY — FIFTH LECTUREReturning to the example, a solution isx = 1 · (3 · 5 · 7 · 11) · 1 + 2 · (2 · 5 · 7 · 11) · 2 + 1 · (2 · 3 · 7 · 11) · 3+ 5 · (2 · 3 · 5 · 11) · 1 + 6 · (2 · 3 · 5 · 7) · 1= 8531= 1601 mod 2310.(It is easy to verify that 13 · 1601 = 23 mod 2310.)2. The Sun Ze Theorem StructurallyAgain let n1, . . . , nkbe pairwise coprime positive integers, and let n be theirproduct. The mapZ −→YiZ/niZ, x 7−→ (x mod n1, . . . , x mod nk)is a ring homomorphism. Its kernel is nZ. So the map descends to an injectionZ/nZ −→YiZ/niZ, x mod n 7−→ (x mod n1, . . . , x mod nk)But this injection surjects as well. One can see this either by counting (both sidesare finite rings with n elements) or by noting that in fact we have constructed theinverse map,YiZ/niZ −→ Z/nZ, (x1mod n1, . . . , xkmod nk) 7−→Xxieimod n.For example, the inverse ofZ/12Z −→ Z/4Z × Z/3Z, x mod 12 7−→ (x mod 4, x mod 3)isZ/4Z × Z/3Z −→ Z/12Z, (x1mod 4, x2mod 3) 7−→ 9x1+ 4x2mod 12.Especially, the the niare prime powers, we have an isomorphismZ/(pe11· · · pekk)Z∼−→ (Z/pe11Z) × · · · × (Z/pekkZ),orZ/(Qppep)Z∼−→YpZ/pepZ.3. The Miller–Rabin Test AgainSuppose that an odd integer n factors as n =Qppep. By the Sun Ze Theorem,the conditionx2= 1 mod nis equivalent to the simultaneous conditionsx2= 1 mod pepfor all p | n,which in turn is equivalent to the simultaneous conditionsx = ±1 mod pepfor all p | n,with all the “±” signs independent of each other. Thus, if n is divisible by k distinctprimes then there are 2ksquare roots of 1 modulo p.MATH 361: NUMBER THEORY — FIFTH LECTURE 3Of these 2ksquare roots of 1 modulo n, only one is −1 modulo n. The Miller–Rabin test returns the result that n could be prime if it finds the particular squareroot −1 of 1 modulo n. The odds of finding −1 rather than some other square rootof 1 are 1/2k, so they are at most 1/4.4. A Simple Thresh-hold Scheme Based on the Sun Ze TheoremLet n1, . . . , nkbe pairwise coprime integers, all large. DefineN = the product of all the ni,n = the product of all the niexcept nk.ThusN /n = nk.Consider a secret numberx : 0 ≤ x < N.Let ai= x%nifor i = 1, . . . , k. Then:All k of the aidetermine x, but the first k − 1 of them do not.Indeed, given a1through ak, the Sun Ze Theorem shows how the congruences˜x = aimod ni, i = 1, . . . , k,give us a value ˜x in {0, · · · , N − 1} that agrees with x modulo N . But also x liesin the same range as ˜x, so they are equal.On the other hand, given only a1through ak−1), we can solve the congruences˜x = aimod ni, i = 1, . . . , k − 1,and so we have a value ˜x ∈ {0, · · · , n − 1} that agrees with x modulo n. But also˜x plus any multiple of n is a candidate for x until we reach N. Thus there areN /n = nkcandidates for x based on