Chinese remainder theorem

The Chinese Remainder Theorem is a tool for solving systems of linear congruences of the following form: $a_{1} x \equiv b_{1} (mod m_{1}), ...., a_{n - 1} x \equiv (mod m_{n - 1}), a_{n} x \equiv b_{n} (mod m_{n})$ .

Theorem 1(Chinese remainder theorem).

Let m $_{1}$ , … , m $_{r}$ be positive integers different from 1 and pairwise relatively prime. Then for any nonzero integers a $_{1}$ , … , a $_{r}$ the system of linear congruences $x \equiv a_{1} (mod m_{1}), ..., x \equiv a_{r} (mod m_{r})$ has integer solutions, with any one of the solutions being congruent modulo $g c d (m_{1}, m_{2} ... m_{r})$ (since they are relatively prime, this will simply evaluate to their product).

Proof
Let there exist a solution $X$ for the system of modular congruences

X = b_{1} (mod n_{1}) X = b_{2} (mod n_{2}) ⋮ X = b_{k} (mod n_{k})

such that $n_{1}, n_{2}, ... n_{k} \in N$ , $g cd (n_{i}, n_{j}) = 1 \forall i \neq = j$ , and $b_{1}, b_{2}, ... b_{k} \in Z$ .

Proof
- to prove→the system of congruences has a unique solution modulo $(n_{1} n_{2} n_{3} ... n_{k})$
- here goes
  - let $N = n_{1} n_{2} n_{3} ... n_{k}$
  - let $N_{i} = \frac{N}{n _{i}}$
  - assertion 1→ $g c d (N_{i}, n_{i}) = 1$
  - assertion 2→if gcd(a, b) = 1 for $a, b \in N$ , there must exist $x, y \in Z$ which satisfy the equation $a x - b y = 1$
  - using assertion 2, we can say that $N_{i} x_{i} - n_{i} y_{i} = 1$ for $x_{i}, y_{i} \in Z$
  - $N_{i} x_{i} = n_{i} y_{i} + 1$
  - the above expression is equivalent to saying $N_{i} x_{i} \equiv 1 (mod n_{i})$ *
  - assertion 3→ $N_{i} x_{i} \equiv 0 (mod n_{j})$ for $i \neq = j$
  - now, consider a solution for X $X = x_{1} N_{1} b_{1} + x_{2} N_{2} b_{2} ... x_{k} N_{k} b_{k}$
  - if we take $(mod n_{i})$ , all terms except $x_{i} N_{i} b_{i}$ will evaluate to 0 (assertion 3)
  - thus, $X \equiv x_{i} N_{i} b_{i} (mod n_{i})$
  - using *, $X \equiv b_{i} (mod n_{i})$
  - thus, $X = x_{1} N_{1} b_{1} + x_{2} N_{2} b_{2} ... x_{k} N_{k} b_{k} = i = 1 \sum k x_{i} N_{i} b_{i}$ is the solution of the system of congruences, congruent modulo $(n_{1} n_{2} n_{3} ... n_{k})$
Method to solve simultaneous congruences using the Chinese Remainder Theorem
- example: $x \equiv 2 (mod 4) x \equiv 3 (mod 5) x \equiv 1 (mod 7)$
- note: all variable references are taken from the proof
- first make sure that 4, 5 and 7 are relatively co-prime. Sure enough, there are. If not, try to break up the congruences.
- let’s define $a_{i} = x_{i} b_{i}$
- then, the solution will reduce to $X = a_{1} N_{1} + a_{2} N_{2} + a_{3} N_{3}$
- compute $N_{i}$ $X = a_{1} (5 \times 7) + a_{2} (4 \times 7) + a_{3} (4 \times 5)$
- now, take $(mod 4), (mod 5), an d (mod 7)$ on both sides to get three equations which you can use to solve for $a_{1}, a_{2},$ and $a_{3}$
- $(mod 4)$ on both sides: $2 \equiv a_{1} (5 \times 7) + 0 + 0 (mod 4)$ $2 = a_{1} (- 1)$ $a_{1} = - 2$
- similarly, $a_{2} = 1$ and $a_{3} = - 1$
- these values for $a_{i}$ are not set in stone, different values will just result in a different solution for X
- finally, use the obtained values to solve for X $X = - 2 (5 \times 7) + 1 (4 \times 7) - 1 (4 \times 5) = - 62$
- the general solution will be $- 62 + 140 t$ , where 140 is $g c d (4, 5, 7)$ and $t \in Z$
- usually, the solution is presented with the lowest natural number solution as the first term. so, the finial answer for X is $78 + 140 t$
- note→if you encounter something like $3 \equiv 2 a_{i} (mod 7)$ , remember that $a_{i}$ needs to be an integer. In this case, add 7 to the LHS repeatedly until the LHS becomes divisible by the coefficient of $a_{i}$ , which is 2 here. thus, $3 + 7 \equiv 2 a_{i} (mod 2) ⟹ a_{i} = 5$

NoNotes

Graph View

Chinese remainder theorem

Backlinks