Recall The Standard Statement Of The Chinese Remainder Theorem

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)