Chinese Remainder Theorem (CRT)

Generally

NOTE

Let $m_{1}, m_{2}, \dots, m_{r}$ be pairwise relatively prime integers and let $M = \prod_{i = 1}^{r} m_{i}$ . For every list $a_{1}, \dots, a_{r}$ with $0 \leq a_{i} < m_{i}$ for $1 \leq i \leq r$ , the system of congruence equations
$⎩ ⎨ ⎧ x \equiv_{m_{1}} a_{1} x \equiv_{m_{2}} a_{2} \dots x \equiv_{m_{r}} a_{r}$
has a unique solution $x$ satisfying $0 \leq x < M$

Case: r=2

NOTE

Let $n_{1}$ and $n_{2}$ be two positive integers that are coprime ( $g cd (n_{1}, n_{2}) = 1$ ). Then for any pair of residues $a_{1}$ and $a_{2}$ , the system

${x \equiv a_{1} (mod n_{1}), x \equiv a_{2} (mod n_{2}),$ has a unique solution modulo $M = n_{1} n_{2} $ .

A simple constructive example

${x \equiv 2 (mod 3), x \equiv 3 (mod 5),$ $M = 3 * 5 = 15$ $M_{i} = M / n :$ $M_{1} = 15/3 = 5, M_{2} = 15/5 = 3$ Find the modular inverse: $M_{i} N_{i} \equiv_{m_{i}} 1$ $N_{1} : 5 N_{1} \equiv 1 (mod 3) ⟹ N_{1} = 2$ $N_{2} : 3 N_{2} \equiv 1 (mod 5) ⟹ N_{2} = 2$ Switch the parts together: ( $r = 2$ the number of equations) $x \equiv_{15} \sum_{i = 1}^{r} a_{i} M_{i} N_{i} \equiv_{15} a_{1} M_{1} N_{1} + a_{2} M_{2} N_{2} \equiv_{15} 2 * 5 * 2 + 3 * 3 * 2 = 38 \equiv_{15} 8 (m o d 15)$ $x = 8 + 15 k, k \in N$

Thomas Second Brain

Explorer

Chinese Remainder Theorem (CRT)

Generally

Case: r=2

A simple constructive example

Graph View

Table of Contents

Backlinks