Question

1.37. The Chinese remainder theorem.
(a) Make a table with three columns. The first column is all numbers from 0 to 14. The second is the residues of these numbers modulo 3; the third column is the residues modulo 5. What do we observe?
(b) Prove that if p and q are distinct primes, then for every pair (j, k) with $\mathbf{0}\mathbf{\le }\mathbf{j}\mathbf{<}\mathbf{q}$and $\mathbf{0}\mathbf{\le }\mathbf{k}\mathbf{<}\mathbf{q}$, there is a unique integer $\mathbf{0}\mathbf{\le }\mathbf{i}\mathbf{<}\mathbf{pq}$such that$\mathbf{i}\mathbf{\equiv }\mathbf{j}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{p}$ and$\mathbf{i}\mathbf{\equiv }\mathbf{k}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{q}$. (Hint:
Prove that no two different i's in this range can have the same (j, k), and then count.)
(c) In this one-to-one correspondence between integers and pairs, it is easy to go from i to (j, k). Prove that the following formula takes we the other way:
$\mathbf{i}\mathbf{=}\left\{j.q\left(q^{-1}\mathrm{mod}p\right)+\mathrm{kp}\left(p^{-1}\mathrm{mod}q\right)\right\}\mathbf{modpq}$
(d) Can we generalize parts (b) and (c) to more than two primes?

Short answer

a) The table with three columns is determined

Numbers From 0 to 14	Modulo 3 (i)	Modulo 5 (j)
0	0	0
1	1	1
2	2	2
3	0	3
4	1	4
5	2	0
6	0	1
7	1	2
8	2	3
9	0	4
10	1	0
11	2	1
12	0	2
13	1	3
14	2	4

b) The total number of pairs is "$\left(\mathrm{p}\times \mathrm{q}\right)$", thus at least two different numbers and i' having the same pair of " (j',k')". and therefore, the proof is a contradiction.

c) From the given formula $\mathrm{i}=\left\{\mathrm{j}\times \mathrm{q}\times \left({\mathrm{q}}^{-1}\mathrm{mod}\mathrm{p}\right)+\mathrm{k}\times \mathrm{p}\times \left({\mathrm{p}}^{-1}\mathrm{mod}\mathrm{q}\right)\right\}\mathrm{mod}\mathrm{pq}$, transitioning from "i" to "j" and "k" is simple.

d) Generalization of the part (b) and part (c) by more than two primes are, "($\mathrm{p}\times \mathrm{q}\times \mathrm{r}$)" or "($\mathrm{p}\times \mathrm{q}\times \mathrm{r}\times \mathrm{s}$)" and,

$$\begin{gathered} \mathrm{i}=\left\{{\mathrm{j}}_1·{\mathrm{q}}_2·{\mathrm{q}}_3·...·{\mathrm{q}}_{\mathrm{n}}\left({\left({\mathrm{q}}_2·{\mathrm{q}}_3·...·{\mathrm{q}}_{\mathrm{n}}\right)}^{-1}\mathrm{mod}{\mathrm{q}}_1\right)+...+\right\} \\ +{\mathrm{j}}_{\mathrm{n}}·{\mathrm{q}}_1·{\mathrm{q}}_2·...·{\mathrm{q}}_{\mathrm{n}-1}\left({\left({\mathrm{q}}_1·{\mathrm{q}}_2·...·{\mathrm{q}}_{\mathrm{n}-1}\right)}^{-1}\mathrm{mod}{\mathrm{q}}_{\mathrm{n}}\right)\mathrm{mod}{\mathrm{p}}_1·{\mathrm{p}}_2·...·{\mathrm{p}}_{\mathrm{n}} \end{gathered}$$

Step-by-step solution

Step 1: Introduction to the Concept

The remainder theorem asserts that when a polynomial, $\mathrm{f}\left(\mathrm{x}\right)$, is divided by a linear polynomial, $\mathrm{x}-\mathrm{a}$, the remainder is the same as $\mathrm{f}\left(\mathrm{a}\right)$.

Generation of a table

a)

Consider the integer "7".

• Find the number "7" modulo "3".
• If we divide the number "7" by the number "3" the leftover will be "1"

Thus $7\mathrm{mod}3=1$.

• Find the number "7" modulo "5".
• When we divide the number "7" by the number "5", the residual is "2."

Thus, $7\mathrm{mod}5=2$.

Consider the number "13":

• Find the number "13" modulo "3".
• If we divide the number "13" by the number "3" the remaining will be "1".

Thus$13\mathrm{mod}=1$

• Find the number "13" modulo "5".
• If we divide the number "13" by the number "5", the leftover is "3."

Thus $13\mathrm{mod}5=3$.

Based on the computations in the previous section, the following table was created.

Numbers From 0 to 14	Modulo 3 (i)	Modulo 5 (j)
0	0	0
1	1	1
2	2	2
3	0	3
4	1	4
5	2	0
6	0	1
7	1	2
8	2	3
9	0	4
10	1	0
11	2	1
12	0	2
13	1	3
14	2	4

Each number from "0" to "14" in the following table contains distinct pairs of residues (i, j) (That is, "i" represents "modulo 3" and "j" represents "modulo 5").

Solution Explanation

b)

Assume that "i" and "'j" have the same pair of values "(j,k)" when the condition “$\mathrm{i}\ne {\mathrm{i}}^{\text{'}}$” is met.

• The two separate integer values are represented by “i” and "i’".
• The value of i can be expressed as:

$\mathrm{i}=\mathrm{Ap}+\mathrm{j}=\mathrm{Bq}+\mathrm{k}$

1. Because "$\mathrm{i}\equiv \mathrm{jmod}\mathrm{p}$" and "$\mathrm{i}\equiv \mathrm{kmod}\mathrm{q}$".
2. As a result, the "i’” can be written as:

${\mathrm{i}}^{\text{'}}=\mathrm{Cp}+\mathrm{j}=\mathrm{Dq}+\mathrm{k}$

1. Because "$\mathrm{i}\equiv \mathrm{j}\mathrm{mod}\mathrm{p}$" and "$\mathrm{i}\equiv \mathrm{k}\mathrm{mod}\mathrm{q}$".
2. Therefore, “$\mathrm{i}\ne {\mathrm{i}}^{\text{'}}$:can be expressed as:

$\begin{array}{rcl}\mathrm{i}-{\mathrm{i}}^{\text{'}}& =& \left(\mathrm{Ap}+\mathrm{j}\right)-\left(\mathrm{Cp}+\mathrm{j}\right)\\ & =& \left(\mathrm{Ap}+\mathrm{j}-\mathrm{Cp}-\mathrm{j}\right)\\ & =& \left(\mathrm{Ap}-\mathrm{Cp}\right)\\ & =& \mathrm{p}\left(\mathrm{A}-\mathrm{C}\right)\end{array}$

• Therefore, “$\mathrm{i}\ne {\mathrm{i}}^{\text{'}}$:can alternatively be expressed as:

$\begin{array}{rcl}\mathrm{i}-{\mathrm{i}}^{\text{'}}& =& \left(\mathrm{Bq}+\mathrm{j}\right)-\left(\mathrm{Dq}+\mathrm{j}\right)\\ & =& \left(\mathrm{Bq}+\mathrm{j}-\mathrm{Dq}-\mathrm{j}\right)\\ & =& \left(\mathrm{Bq}-\mathrm{Dq}\right)\\ & =& \mathrm{q}\left(\mathrm{B}-\mathrm{D}\right)\end{array}$

• Therefore, “$\mathrm{i}-{\mathrm{i}}^{\text{'}}=\mathrm{p}\left(\mathrm{A}-\mathrm{C}\right)=\mathrm{q}\left(\mathrm{B}-\mathrm{D}\right)$.

"p" and "q" are different primes, hence (A-C) must be divided by "q," and (B-D) must be divided by "p," as seen in the given statement:

$\begin{array}{rcl}\mathrm{i}-{\mathrm{i}}^{\text{'}}& =& \mathrm{p}\left(\mathrm{A}-\mathrm{C}\right)=\mathrm{q}\left(\mathrm{B}-\mathrm{D}\right)\\ & =& \frac{\left(\mathrm{A}-\mathrm{C}\right)}{\mathrm{q}}=\frac{\left(\mathrm{B}-\mathrm{D}\right)}{\mathrm{p}}\\ & & \end{array}$

• As a result, "$\mathrm{i}-{\mathrm{i}}^{\text{'}}=0\mathrm{mod}\mathrm{pq}$"
• This demonstrates that "$\mathrm{i}-{\mathrm{i}}^{\text{'}}$" with "i" and "i’" is less than"$\left(\mathrm{p}\times \mathrm{q}\right)$".

The total number of pairs is "$\left(\mathrm{p}\times \mathrm{q}\right)$" implying that at least two separate numbers i and i’ share a pair of "(j',k')".

• As a result, the proof is incongruence.

Solution Explanation

c)

The value of "i" can be rendered as follows based on part (b):

$\mathrm{i}=\mathrm{j}\mathrm{mod}\mathrm{p}\mathrm{and}\mathrm{i}=\mathrm{k}\mathrm{mod}\mathrm{q}-------\left(1\right)$

The provided formula can be written as follows based on equation (1):

$\mathrm{i}=\left\{\mathrm{j}.\mathrm{q}.\left({\mathrm{q}}^{-1}\mathrm{mod}\mathrm{p}\right)+\mathrm{k}.\mathrm{p}.\left({\mathrm{p}}^{-1}\mathrm{mod}\mathrm{q}\right)\right\}\mathrm{mod}\mathrm{pq}$

Write the above equation using the equation (1) pattern.

$\begin{array}{rcl}\mathrm{i}& =& \left\{\mathrm{j}.\mathrm{q}.\left({\mathrm{q}}^{-1}\mathrm{mod}\mathrm{p}\right)+\mathrm{k}.\mathrm{p}\left({\mathrm{p}}^{-1}\mathrm{mod}\mathrm{q}\right)\right\}\mathrm{mod}\mathrm{pq}\mathrm{mod}\mathrm{p}\\ & =& \left\{\mathrm{j}.\mathrm{q}.\left({\mathrm{q}}^{-1}\mathrm{mod}\mathrm{p}\right)+\mathrm{k}.\mathrm{p}\left({\mathrm{p}}^{-1}\mathrm{mod}\mathrm{q}\right)\right\}\mathrm{mod}\mathrm{p}\mathrm{mod}\mathrm{pq}\\ & =& \mathrm{j}\end{array}$

The following is another way to write the above equation:

$\begin{array}{rcl}\mathrm{i}& =& \left\{\mathrm{j}.\mathrm{q}.\left({\mathrm{q}}^{-1}\mathrm{mod}\mathrm{p}\right)+\mathrm{k}.\mathrm{p}\left({\mathrm{p}}^{-1}\mathrm{mod}\mathrm{q}\right)\right\}\mathrm{mod}\mathrm{pq}\mathrm{mod}\mathrm{q}\\ & =& \left\{\mathrm{j}.\mathrm{q}.\left({\mathrm{q}}^{-1}\mathrm{mod}\mathrm{p}\right)+\mathrm{k}.\mathrm{p}\left({\mathrm{p}}^{-1}\mathrm{mod}\mathrm{q}\right)\right\}\mathrm{mod}\mathrm{q}\mathrm{mod}\mathrm{pq}\\ & =& \mathrm{k}\end{array}$

As a result, transitioning from "i" to "j" and "k" is simple.

Solution Explanation

d)

• Part (b) can be expanded to include more than two primes, such as

"($\mathrm{p}\times \mathrm{q}\times \mathrm{r}$)" or "($\mathrm{p}\times \mathrm{q}\times \mathrm{r}\times \mathrm{s}$)".

• Extending part (c) by improving the phrasing of “i” as follows:

$$\begin{gathered} \mathrm{i}=\left\{{\mathrm{j}}_1·{\mathrm{q}}_2·{\mathrm{q}}_3·...·{\mathrm{q}}_{\mathrm{n}}\left({\left({\mathrm{q}}_2·{\mathrm{q}}_3·...·{\mathrm{q}}_{\mathrm{n}}\right)}^{-1}\mathrm{mod}{\mathrm{q}}_1\right)+...+\right\} \\ +{\mathrm{j}}_{\mathrm{n}}·{\mathrm{q}}_1·{\mathrm{q}}_2·...·{\mathrm{q}}_{\mathrm{n}-1}\left({\left({\mathrm{q}}_1·{\mathrm{q}}_2·...·{\mathrm{q}}_{\mathrm{n}-1}\right)}^{-1}\mathrm{mod}{\mathrm{q}}_{\mathrm{n}}\right)\mathrm{mod}{\mathrm{p}}_1·{\mathrm{p}}_2·...·{\mathrm{p}}_{\mathrm{n}} \end{gathered}$$

1. Here, it's combining various sets of "part (c)" values.