Chinese remainder

Chinese remainder theorem (also called Chinese remainder class theorem ) is the name of several similar theorems in abstract algebra and number theory .

Simultaneous congruences of whole numbers

A simultaneous congruence of integers is a system of linear congruences

${\displaystyle {\begin{matrix}x&\equiv &a_{1}&{\pmod {m_{1}}}\\x&\equiv &a_{2}&{\pmod {m_{2}}}\\&\vdots &&\\x&\equiv &a_{n}&{\pmod {m_{n}}}\\\end{matrix}}}$

for which all are to be determined who solve all congruences at the same time. If a solution exists, then with LCM the numbers are exactly all the solutions. But it can also be that there is no solution at all. ${\displaystyle x}$ ${\displaystyle x_{0}}$ ${\displaystyle M:=}$ ${\displaystyle (m_{1},m_{2},m_{3},\ldots ,m_{n})}$ ${\displaystyle x_{0}+kM\ (k\in \mathbb {Z} )}$

Coprime modules

Derivation

The original form of the Chinese remainder of the sentence comes from the book Sūn Zǐ Suànjīng ( Chinese  孫子 算 經  /  孙子 算 经  - "Sun Zi's Handbook of Arithmetic") by the mathematician Sun Zi (probably 3rd century) and was written in 1247 by Qin Jiushao's Shùshū Jiǔzhāng ( 數 書 九章  /  数 书 九章  - "Mathematical Treatise in Nine Chapters") republished. The theorem makes a statement about simultaneous congruences for the case that the modules are coprime . It is:

Let pairwise coprime natural numbers exist, then for every tuple of integers there exists an integer that satisfies the following simultaneous congruence: ${\displaystyle m_{1},\ldots ,m_{n}}$ ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle x}$

${\displaystyle x\equiv a_{i}\mod m_{i}}$ For ${\displaystyle i=1,\ldots ,n}$

All solutions to this congruence are congruent modulo . ${\displaystyle M:=m_{1}m_{2}m_{3}\ldots m_{n}}$

The product here agrees with the LCM because of the coprime nature . ${\displaystyle M}$

Find a solution

A solution can be found as follows: For each the numbers and are prime, so one can e.g. B. with the extended Euclidean algorithm find two whole numbers and such that ${\displaystyle x}$ ${\displaystyle i}$ ${\displaystyle m_{i}}$ ${\displaystyle M_{i}:=M/m_{i}}$ ${\displaystyle r_{i}}$ ${\displaystyle s_{i}}$

${\displaystyle r_{i}\cdot m_{i}+s_{i}\cdot M_{i}=1}$.

Bet , then applies ${\displaystyle e_{i}:=s_{i}\cdot M_{i}}$

${\displaystyle e_{i}\equiv 1\mod m_{i}}$

${\displaystyle e_{i}\equiv 0\mod m_{j},\ j\neq i}$.

The number

${\displaystyle x:=\sum _{i=1}^{n}a_{i}e_{i}}$

is then a solution of simultaneous congruence.

example

Find an integer with the property ${\displaystyle x}$

${\displaystyle {\begin{matrix}x&\equiv &2&{\pmod {3}}\\x&\equiv &3&{\pmod {4}}\\x&\equiv &2&{\pmod {5}}\\\end{matrix}}}$

Here is . With the help of the extended Euclidean algorithm one calculates ${\displaystyle M=3\cdot 4\cdot 5=60,\ M_{1}=M/3=20,\ M_{2}=M/4=15,\ M_{3}=M/5=12}$

${\displaystyle 7\cdot 3+(-1)\cdot 20=1}$, so ${\displaystyle e_{1}=-20}$

${\displaystyle 4\cdot 4+(-1)\cdot 15=1}$, so ${\displaystyle e_{2}=-15}$

${\displaystyle 5\cdot 5+(-2)\cdot 12=1}$, so ${\displaystyle e_{3}=-24}$

One solution is then . Because of this , all other solutions are congruent to 47 modulo 60. ${\displaystyle x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133}$ ${\displaystyle -133\equiv 47\mod 60}$

General case

A solution sometimes also exists in the event that the modules are not relatively prime. The exact condition reads: A solution of the simultaneous congruence exists if and only if the following applies to all : ${\displaystyle i\neq j}$

${\displaystyle a_{i}\equiv a_{j}\mod {}}$ GCD . ${\displaystyle (m_{i},m_{j})}$

All solutions are then congruent modulo the LCM of . ${\displaystyle m_{i}}$

A simultaneous congruence can be achieved in the case of the existence of a solution e.g. B. solve by successive substitution , even if the modules are not coprime.

example

A classic puzzle is to find the smallest natural number that, when divided by 2, 3, 4, 5, and 6 leaves the remainder 1 and is divisible by 7 . We are looking for the smallest positive solution of the simultaneous congruence ${\displaystyle x}$

${\displaystyle {\begin{matrix}x&\equiv &1&\mod 2\\x&\equiv &1&\mod 3\\x&\equiv &1&\mod 4\\x&\equiv &1&\mod 5\\x&\equiv &1&\mod 6\\x&\equiv &0&\mod 7\\\end{matrix}}}$

Since the modules are not relatively prime, the Chinese remainder of the law cannot be used directly (with the solution method). But the first five conditions can be summarized as : H. to find a solution is from ${\displaystyle x\equiv 1\mod \operatorname {kgV} (2,3,4,5,6)}$

${\displaystyle {\begin{matrix}x&\equiv &1&\mod 60\\x&\equiv &0&\mod 7\\\end{matrix}}}$

This congruence system can now be solved with the Chinese remainder of the sentence. The solutions are congruent to 301 modulo 420.

Direct solving of simultaneous congruences of integers

The two simultaneous congruences are given:

${\displaystyle {\begin{matrix}x&\equiv &a&{\pmod {n}}\\x&\equiv &b&{\pmod {m}}\\\end{matrix}}}$

If these are solvable, that is , they are equivalent to the simple congruence: ${\displaystyle a\equiv b{\pmod {d}}}$

${\displaystyle {\begin{matrix}x&\equiv &a-yn{\frac {a-b}{d}}&{\pmod {\frac {nm}{d}}}\\\end{matrix}}}$

With

${\displaystyle d=\operatorname {ggT} (n,m)=yn+zm}$.

This also works with non prime numbers n and m and thus makes it much easier to solve simultaneous congruences.

A system of congruences can be solved by repeatedly applying this simplification.

Statement for main ideal rings

Let be a main ideal ring , then the residual Chinese theorem for is as follows: ${\displaystyle R}$ ${\displaystyle R}$

If pairs are coprime and their product, then the factor ring is isomorphic to the product ring due to the isomorphism ${\displaystyle m_{1},\ldots ,m_{n}}$ ${\displaystyle m}$ ${\displaystyle R/mR}$ ${\displaystyle R/m_{1}R\times \cdots \times R/m_{n}R}$

${\displaystyle {\begin{matrix}f:&R/mR&\to &R/m_{1}R\times \cdots \times R/m_{n}R\\&x+mR&\mapsto &(x+m_{1}R,\ldots ,x+m_{n}R)\end{matrix}}}$

Statement for general rings

One of the most general forms of the Chinese remainder is a formulation for any ring (with a single element). ${\displaystyle R}$

Are (bilateral) ideals such that for (the ideals are then called coprime or coprime), and be the average of the ideals, then the factor ring is isomorphic to the product ring through the isomorphism ${\displaystyle I_{1},\ldots ,I_{n}}$ ${\displaystyle I_{i}+I_{j}=R}$ ${\displaystyle i\neq j}$ ${\displaystyle I}$ ${\displaystyle R/I}$ ${\displaystyle R/I_{1}\times \cdots \times R/I_{n}}$

${\displaystyle {\begin{matrix}f:&R/I&\to &R/I_{1}\times \cdots \times R/I_{n}\\&x+I&\mapsto &(x+I_{1},\ldots ,x+I_{n}).\end{matrix}}}$

( is also equal to the product of if is a commutative ring.) ${\displaystyle I}$ ${\displaystyle I_{j}}$ ${\displaystyle R}$

Web links

Wikibooks: Proof of the sentence in the evidence archive  - learning and teaching materials

• Program for calculating simultaneous congruences
• Chinese Remainder Theorem in the Encyclopaedia of Mathematics
• Eric W. Weisstein : Chinese Remainder Theorem . In: MathWorld (English).
• Christian Spannagel : Chinese remainder of the sentence . Lecture series, 2012.
• Chinese Remainder Theorem. Planetmath.org (English).

Individual evidence

1. ^ JJ O'Connor, EF Robertson: Sun Zi biography. School of Mathematics and Statistics, University of St Andrews, Scotland, accessed August 5, 2010 . 
2. ↑ H. Gericke gives a possible period between 280 and 473 AD. (H. Gericke: Mathematik in Antike, Orient und Abendland. Springer, Berlin 1990, section 3.1, p. 182)
3. ↑ A proof that this condition is sufficient can be found in A. Bogomolny: Chinese Remainder Theorem , Theorem 2 on Interactive Mathematics Miscellany and Puzzles (English); the need is easy to see.