# Recall The Standard Statement Of The Chinese Remainder Theorem

1385 Words
6 Pages

The Quotient Ring Transform is an alternate encoding and decoding process developed by Dr. Anna

Johnston [5]. The utility of this error detection and correction process is that it is not dependent on a fixed set of primitive roots. Thus, a standard encryption procedure can be efficiently included in the process. This section lays out Dr. Johnston’s work and provides a simple worked example.

3.1 The Chinese Remainder Theorem

Recall the standard statement of the Chinese Remainder Theorem [1]:

Theorem 3.1 (Chinese Remainder Theorem). Let n1, n2, . . . , nk ∈ Z with every ni pairwise coprime and ni > 1. Let N = n1n2 . . . nk. Then there exists a unique x ∈ Z with 0 ≤ x < N such that x ≡ a1 mod n1 x ≡ a2 mod n2

.

.

.

x ≡ ak mod nk

Stated another way, Z/NZ ∼= Z/n1Z×· · ·×Z/nkZ given by x mod N 7→ (x mod n1, . . . , x mod nk) is a ring homomorphism.

Proof. Let N = n1n2 . . . nk, yi =

N

ni for all i = 1, 2, . . . , k, and zi = y

−1

i mod ni

. Note that y

−1

i mod ni exist since yi and ni are coprime by construction. Notice that when j 6= r, yjzj ≡ 0 mod nr and when j = r, yjzj ≡ 1 mod nr. Then x =

X

k i=1 aiyizi (7) satisfies all of the congruences in the statement of the theorem.

6

For example, suppose we want to find x such that x ≡ 1 mod 5 x ≡ 3 mod 7 x ≡ 2 mod 9.

We then have that N = (5)(7)(9) = 315 and y1 = 315/5 = 63, y2 = 315/7 = 45, and y3 = 315/9 = 35.

This gives us that

2 ≡ 63−1 mod 5

5 ≡ 45−1 mod 7

8 ≡ 35−1 mod 9 and so z1 = 2, z2 = 5, and z3 = 8. Therefore, x = 1(63)(2)

Johnston [5]. The utility of this error detection and correction process is that it is not dependent on a fixed set of primitive roots. Thus, a standard encryption procedure can be efficiently included in the process. This section lays out Dr. Johnston’s work and provides a simple worked example.

3.1 The Chinese Remainder Theorem

Recall the standard statement of the Chinese Remainder Theorem [1]:

Theorem 3.1 (Chinese Remainder Theorem). Let n1, n2, . . . , nk ∈ Z with every ni pairwise coprime and ni > 1. Let N = n1n2 . . . nk. Then there exists a unique x ∈ Z with 0 ≤ x < N such that x ≡ a1 mod n1 x ≡ a2 mod n2

.

.

.

x ≡ ak mod nk

Stated another way, Z/NZ ∼= Z/n1Z×· · ·×Z/nkZ given by x mod N 7→ (x mod n1, . . . , x mod nk) is a ring homomorphism.

Proof. Let N = n1n2 . . . nk, yi =

N

ni for all i = 1, 2, . . . , k, and zi = y

−1

i mod ni

. Note that y

−1

i mod ni exist since yi and ni are coprime by construction. Notice that when j 6= r, yjzj ≡ 0 mod nr and when j = r, yjzj ≡ 1 mod nr. Then x =

X

k i=1 aiyizi (7) satisfies all of the congruences in the statement of the theorem.

6

For example, suppose we want to find x such that x ≡ 1 mod 5 x ≡ 3 mod 7 x ≡ 2 mod 9.

We then have that N = (5)(7)(9) = 315 and y1 = 315/5 = 63, y2 = 315/7 = 45, and y3 = 315/9 = 35.

This gives us that

2 ≡ 63−1 mod 5

5 ≡ 45−1 mod 7

8 ≡ 35−1 mod 9 and so z1 = 2, z2 = 5, and z3 = 8. Therefore, x = 1(63)(2)