Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.4 The Chinese Remainder Theorem

In many situations, it is useful to break a congruence mod $n$ $n$ into a system of congruences mod factors of $n .$ $n .$ Consider the following example. Suppose we know that a number $x$ $x$ satisfies $x \equiv 25 (mod 42) .$ $x \equiv 25 (mod 42) .$ This means that we can write $x = 25 + 42 k$ $x = 25 + 42 k$ for some integer $k .$ $k .$ Rewriting 42 as $7 \cdot 6,$ $7 \cdot 6,$ we obtain $x = 25 + 7 (6 k),$ $x = 25 + 7 (6 k),$ which implies that $x \equiv 25 \equiv 4 (mod 7) .$ $x \equiv 25 \equiv 4 (mod 7) .$ Similarly, since $x = 25 + 6 (7 k),$ $x = 25 + 6 (7 k),$ we have $x \equiv 25 \equiv 1 (mod 6) .$ $x \equiv 25 \equiv 1 (mod 6) .$ Therefore,

\begin{matrix} x \equiv 25 & (mod 42) & \Rightarrow & {\begin{array}{l} x \equiv 4 & (mod 7) \\ x \equiv 1 & (mod 6) . \end{array} \end{matrix}

$\begin{matrix} x \equiv 25 & (mod 42) & \Rightarrow & {\begin{array}{l} x \equiv 4 & (mod 7) \\ x \equiv 1 & (mod 6) . \end{array} \end{matrix}$

The Chinese remainder theorem shows that this process can be reversed; namely, a system of congruences can be replaced by a single congruence under certain conditions.

Chinese Remainder Theorem

Suppose $gcd (m, n) = 1 .$ $gcd (m, n) = 1 .$ Given integers $a$ $a$ and $b,$ $b,$ there exists exactly one solution $x (mod m n)$ $x (mod m n)$ to the simultaneous congruences

\begin{array}{l} x \equiv a & (mod m), & x \equiv b & (mod n) . \end{array}

$\begin{array}{l} x \equiv a & (mod m), & x \equiv b & (mod n) . \end{array}$

Proof. There exist integers $s, t$ $s, t$ such that $m s + n t = 1 .$ $m s + n t = 1 .$ Then $m s \equiv 1 (mod n)$ $m s \equiv 1 (mod n)$ and $n t \equiv 1 (mod m) .$ $n t \equiv 1 (mod m) .$ Let $x = b m s + a n t .$ $x = b m s + a n t .$ Then $x \equiv a n t \equiv a (mod m),$ $x \equiv a n t \equiv a (mod m),$ and $x \equiv b m s \equiv b (mod n),$ $x \equiv b m s \equiv b (mod n),$ so a solution $x$ $x$ exists. Suppose $x_{1}$ $x_{1}$ is another solution. Then $x \equiv x_{1} (mod m)$ $x \equiv x_{1} (mod m)$ and $x \equiv x_{1} (mod n),$ $x \equiv x_{1} (mod n),$ so $x - x_{1}$ $x - x_{1}$ is a multiple of both $m$ $m$ and $n .$ $n .$

Lemma

Let $m, n$ $m, n$ be integers with $gcd (m, n) = 1 .$ $gcd (m, n) = 1 .$ If an integer $c$ $c$ is a multiple of both $m$ $m$ and $n,$ $n,$ then $c$ $c$ is a multiple of $m n .$ $m n .$

Proof. Let $c = m k = n ℓ .$ $c = m k = n ℓ .$ Write $m s + n t = 1$ $m s + n t = 1$ with integers $s, t .$ $s, t .$ Multiply by $c$ $c$ to obtain $c = c m s + c n t = m n ℓ s + m n k t = m n (ℓ s + k t) .$ $c = c m s + c n t = m n ℓ s + m n k t = m n (ℓ s + k t) .$

To finish the proof of the theorem, let $c = x - x_{1}$ $c = x - x_{1}$ in the lemma to find that $x - x_{1}$ $x - x_{1}$ is a multiple of $m n .$ $m n .$ Therefore, $x \equiv x_{1} (mod m n) .$ $x \equiv x_{1} (mod m n) .$ This means that any two solutions $x$ $x$ to the system of congruences are congruent mod $m n,$ $m n,$ as claimed.

Example

Solve $x \equiv 3 (mod 7), x \equiv 5 (mod 15) .$ $x \equiv 3 (mod 7), x \equiv 5 (mod 15) .$

SOLUTION

$x \equiv 80 (mod 105)$ $x \equiv 80 (mod 105)$ (note: $105 = 7 \cdot 15$ $105 = 7 \cdot 15$ ). Since $80 \equiv 3 (mod 7)$ $80 \equiv 3 (mod 7)$ and $80 \equiv 5 (mod 15),$ $80 \equiv 5 (mod 15),$ 80 is a solution. The theorem guarantees that such a solution exists, and says that it is uniquely determined mod the product $m n,$ $m n,$ which is 105 in the present example.

How does one find the solution? One way, which works with small numbers $m$ $m$ and $n,$ $n,$ is to list the numbers congruent to $b (mod n)$ $b (mod n)$ until you find one that is congruent to $a (mod m) .$ $a (mod m) .$ For example, the numbers congruent to $5 (mod 15)$ $5 (mod 15)$ are

5, 20, 35, 50, 65, 80, 95, \dots .

$5, 20, 35, 50, 65, 80, 95, \dots .$

Mod 7, these are $5, 6, 0, 1, 2, 3, 4, \dots .$ $5, 6, 0, 1, 2, 3, 4, \dots .$ Since we want $3 (mod 7),$ $3 (mod 7),$ we choose 80.

For slightly larger numbers $m$ $m$ and $n,$ $n,$ making a list would be inefficient. However, the proof of the theorem gives a fast method for finding $x :$ $x :$

Use the Extended Euclidean algorithm to find $s$ $s$ and $t$ $t$ with $m s + n t = 1 .$ $m s + n t = 1 .$
Let $x \equiv b m s + a n t (mod m n) .$ $x \equiv b m s + a n t (mod m n) .$

Example

Solve $x \equiv 7 (mod 12345), x \equiv 3 (mod 11111) .$ $x \equiv 7 (mod 12345), x \equiv 3 (mod 11111) .$

SOLUTION

First, we know from our calculations in Section 3.2 that

12345 \cdot (- 2224) + 11111 \cdot 2471 = 1,

$12345 \cdot (- 2224) + 11111 \cdot 2471 = 1,$

so $s = - 2224$ $s = - 2224$ and $t = 2471 .$ $t = 2471 .$ Therefore, $x \equiv 3 \cdot 12345 \cdot (- 2224) + 7 \cdot 11111 \cdot 2471 \equiv 109821127 (mod (11111 \cdot 12345)) .$ $x \equiv 3 \cdot 12345 \cdot (- 2224) + 7 \cdot 11111 \cdot 2471 \equiv 109821127 (mod (11111 \cdot 12345)) .$

How do you use the Chinese remainder theorem? The main idea is that if you start with a congruence mod a composite number $n,$ $n,$ you can break it into simultaneous congruences mod each prime power factor of $n,$ $n,$ then recombine the resulting information to obtain an answer mod $n .$ $n .$ The advantage is that often it is easier to analyze congruences mod primes or mod prime powers than to work mod composite numbers.

Suppose you want to solve $x^{2} \equiv 1 (mod 35) .$ $x^{2} \equiv 1 (mod 35) .$ Note that $35 = 5 \cdot 7 .$ $35 = 5 \cdot 7 .$ We have

\begin{array}{l} x^{2} \equiv 1 & (mod 35) & \Leftrightarrow & {\begin{array}{l} x^{2} \equiv 1 & (mod 7) \\ x^{2} \equiv 1 & (mod 5) . \end{array} \end{array}

$\begin{array}{l} x^{2} \equiv 1 & (mod 35) & \Leftrightarrow & {\begin{array}{l} x^{2} \equiv 1 & (mod 7) \\ x^{2} \equiv 1 & (mod 5) . \end{array} \end{array}$

Now, $x^{2} \equiv 1 (mod 5)$ $x^{2} \equiv 1 (mod 5)$ has two solutions: $x \equiv \pm 1 (mod 5) .$ $x \equiv \pm 1 (mod 5) .$ Also, $x^{2} \equiv 1 (mod 7)$ $x^{2} \equiv 1 (mod 7)$ has two solutions: $x \equiv \pm 1 (mod 7) .$ $x \equiv \pm 1 (mod 7) .$ We can put these together in four ways:

\begin{array}{l} x & \equiv & 1 & (mod 5), & x & \equiv & 1 & (mod 7) & \to & x & \equiv & 1 & (mod 35), \\ x & \equiv & 1 & (mod 5), & x & \equiv & - 1 & (mod 7) & \to & x & \equiv & 6 & (mod 35), \\ x & \equiv & - 1 & (mod 5), & x & \equiv & 1 & (mod 7) & \to & x & \equiv & 29 & (mod 35), \\ x & \equiv & - 1 & (mod 5), & x & \equiv & - 1 & (mod 7) & \to & x & \equiv & 34 & (mod 35) . \end{array}

$\begin{array}{l} x & \equiv & 1 & (mod 5), & x & \equiv & 1 & (mod 7) & \to & x & \equiv & 1 & (mod 35), \\ x & \equiv & 1 & (mod 5), & x & \equiv & - 1 & (mod 7) & \to & x & \equiv & 6 & (mod 35), \\ x & \equiv & - 1 & (mod 5), & x & \equiv & 1 & (mod 7) & \to & x & \equiv & 29 & (mod 35), \\ x & \equiv & - 1 & (mod 5), & x & \equiv & - 1 & (mod 7) & \to & x & \equiv & 34 & (mod 35) . \end{array}$

So the solutions of $x^{2} \equiv 1 (mod 35)$ $x^{2} \equiv 1 (mod 35)$ are $x \equiv 1, 6, 29, 34 (mod 35) .$ $x \equiv 1, 6, 29, 34 (mod 35) .$

In general, if $n = p_{1} p_{2} \dots p_{r}$ $n = p_{1} p_{2} \dots p_{r}$ is the product of $r$ $r$ distinct odd primes, then $x^{2} \equiv 1 (mod n)$ $x^{2} \equiv 1 (mod n)$ has $2^{r}$ $2^{r}$ solutions. This is a consequence of the following.

Chinese Remainder Theorem (General Form)

Let $m_{1}, \dots, m_{k}$ $m_{1}, \dots, m_{k}$ be integers with $gcd (m_{i}, m_{j}) = 1$ $gcd (m_{i}, m_{j}) = 1$ whenever $i \neq j .$ $i \neq j .$ Given integers $a_{1}, \dots,$ $a_{1}, \dots,$ $a_{k},$ $a_{k},$ there exists exactly one solution $x (mod m_{1} \dots m_{k})$ $x (mod m_{1} \dots m_{k})$ to the simultaneous congruences

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k}) .

$x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k}) .$

For example, the theorem guarantees there is a solution to the simultaneous congruences

x \equiv 1 (mod 11), x \equiv - 1 (mod 13), x \equiv 1 (mod 17) .

$x \equiv 1 (mod 11), x \equiv - 1 (mod 13), x \equiv 1 (mod 17) .$

In fact, $x \equiv 1871 (mod 11 \cdot 13 \cdot 17)$ $x \equiv 1871 (mod 11 \cdot 13 \cdot 17)$ is the answer.

Exercise 57 gives a method for computing the number $x$ $x$ in the theorem.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.4 The Chinese Remainder Theorem

Create new playlist

Sign In

Sign Up

Table of Contents for
3.4 The Chinese Remainder Theorem