The Chinese remainder theorem

Bricogne, G.

doi:10.1107/97809553602060000551

International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 51-52 | 1 | 2 |

Section 1.3.3.2.2.2. The Chinese remainder theorem

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.3.2.2.2. The Chinese remainder theorem

| top | pdf |

Let $[N = N_{1} N_{2} \ldots N_{d}]$ be factored into a product of pairwise coprime integers, so that g.c.d. $[(N_{i}, N_{j}) = 1]$ for $[i \neq j]$ . Then the system of congruence equations $[{\ell} \equiv {\ell}_{j} \hbox{ mod } N_{j},\qquad j = 1, \ldots, d,]$ has a unique solution $[\ell]$ mod N. In other words, each $[\ell \in {\bb Z}/N {\bb Z}]$ is associated in a one-to-one fashion to the d-tuple $[(\ell_{1}, \ell_{2}, \ldots, \ell_{d})]$ of its residue classes in $[{\bb Z}/N_{1} {\bb Z}, {\bb Z}/N_{2} {\bb Z}, \ldots, {\bb Z}/N_{d} {\bb Z}]$ .

The proof of the CRT goes as follows. Let $[Q_{j} = {N \over N_{j}} = {\prod\limits_{i \neq j}}\; N_{i}.]$ Since g.c.d. $[(N_{j}, Q_{j}) = 1]$ there exist integers $[n_{j}]$ and $[q_{j}]$ such that $[n_{j} N_{j} + q_{j} Q_{j} = 1,\qquad j = 1, \ldots, d,]$ then the integer $[{\ell} = {\textstyle\sum\limits_{i = 1}^{d}}\; {\ell}_{i} q_{i} Q_{i} \hbox{ mod } N]$ is the solution. Indeed, $[{\ell} \equiv {\ell}_{j} q_{j} Q_{j} \hbox{ mod } N_{j}]$ because all terms with $[i \neq j]$ contain $[N_{j}]$ as a factor; and $[q_{j} Q_{j} \equiv 1 \hbox{ mod } N_{j}]$ by the defining relation for $[q_{j}]$ .

It may be noted that $[\eqalign{(q_{i} Q_{i}) (q_{j} Q_{j}) &\equiv 0{\phantom{Q_j}}\quad\quad\hbox{ mod } N \hbox{ for } i \neq j,\cr (q_{j} Q_{j})^{2} &\equiv q_{j} Q_{j}\quad\quad\hbox{mod } N, \;\;j = 1, \ldots, d,}]$ so that the $[q_{j} Q_{j}]$ are mutually orthogonal idempotents in the ring $[{\bb Z}/N {\bb Z}]$ , with properties formally similar to those of mutually orthogonal projectors onto subspaces in linear algebra. The analogy is exact, since by virtue of the CRT the ring $[{\bb Z}/N {\bb Z}]$ may be considered as the direct product $[{\bb Z}/N_{1} {\bb Z} \times {\bb Z}/N_{2} {\bb Z} \times \ldots \times {\bb Z}/N_{d} {\bb Z}]$ via the two mutually inverse mappings:

(i) $[{\ell} \;\longmapsto\; (\ell_{1}, \ell_{2}, \ldots, \ell_{d})]$ by $[\ell \equiv \ell_{j}]$ mod $[N_{j}]$ for each j;
(ii) $[(\ell_{1}, \ell_{2}, \ldots, \ell_{d}) \;\longmapsto\; \ell \hbox { by } \ell = {\textstyle\sum_{i = 1}^{d}} \ell_{i} q_{i} Q_{i}\hbox{ mod } N]$ .

The mapping defined by (ii) is sometimes called the `CRT reconstruction' of $[\ell]$ from the $[\ell_{j}]$ .

These two mappings have the property of sending sums to sums and products to products, i.e: $[\displaylines{\quad (\hbox{i})\hfill {\ell} + {\ell}' \;\longmapsto\; ({\ell}_{1} + {\ell}'_{1}, {\ell}_{2} + {\ell}'_{2}, \ldots, {\ell}_{d} + {\ell}'_{d}) \hfill\cr \hfill {\ell} {\ell}' \;\longmapsto\; ({\ell}_{1} {\ell}'_{1}, {\ell}_{2} {\ell}'_{2}, \ldots, {\ell}_{d} {\ell}'_{d}) \quad\;\;\; \phantom{(\hbox{i})} \hfill\cr \quad (\hbox{ii}) \hfill ({\ell}_{1} + {\ell}'_{1}, {\ell}_{2} + {\ell}'_{2}, \ldots, {\ell}_{d} + {\ell}'_{d}) \;\longmapsto\; {\ell} + {\ell}' \;\;\hfill\cr \hfill ({\ell}_{1} {\ell}'_{1}, {\ell}_{2} {\ell}'_{2}, \ldots, {\ell}_{d} {\ell}'_{d}) \;\longmapsto\; {\ell} {\ell}' \quad \phantom{(\hbox{i})} \;\;\;\;\hfill}]$ (the last proof requires using the properties of the idempotents $[q_{j} Q_{j}]$ ). This may be described formally by stating that the CRT establishes a ring isomorphism: $[{\bb Z}/N {\bb Z} \cong ({\bb Z}/N_{1} {\bb Z}) \times \ldots \times ({\bb Z}/N_{d} {\bb Z}).]$

References

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 51-52