Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, p. 54   | 1 | 2 |

Section The Chinese remainder theorem

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France 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)[link] 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})\quad\quad{\ell} + {\ell}' \,\longmapsto\, ({\ell}_{1} + {\ell}'_{1}, {\ell}_{2} + {\ell}'_{2}, \ldots, {\ell}_{d} + {\ell}'_{d}) \hfill\cr \quad\quad\quad\phantom{(\hbox{i})}{\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}) \quad\quad\! ({\ell}_{1} + {\ell}'_{1}, {\ell}_{2} + {\ell}'_{2}, \ldots, {\ell}_{d} + {\ell}'_{d}) \,\longmapsto\, {\ell} + {\ell}' \,\,\hfill\cr \quad\quad\! \phantom{(\hbox{ii})}\quad({\ell}_{1} {\ell}'_{1}, {\ell}_{2} {\ell}'_{2}, \ldots, {\ell}_{d} {\ell}'_{d}) \,\longmapsto\, {\ell} {\ell}' \quad  \,\,\,\,\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}).]

to end of page
to top of page