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
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.
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:
All solutions to this congruence are congruent modulo .
The product here agrees with the LCM because of the coprime nature .
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
Bet , then applies
is then a solution of simultaneous congruence.
Find an integer with the property
Here is . With the help of the extended Euclidean algorithm one calculates
One solution is then . Because of this , all other solutions are congruent to 47 modulo 60.
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 :
All solutions are then congruent modulo the LCM of .
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.
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
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
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:
If these are solvable, that is , they are equivalent to the simple congruence:
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:
If pairs are coprime and their product, then the factor ring is isomorphic to the product ring due to the isomorphism
Statement for general rings
One of the most general forms of the Chinese remainder is a formulation for any ring (with a single element).
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
( is also equal to the product of if is a commutative ring.)
^ JJ O'Connor, EF Robertson: Sun Zi biography. School of Mathematics and Statistics, University of St Andrews, Scotland, accessed August 5, 2010 .
↑ 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)
↑ 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.