Chinese remainder theorem

Chinese Remainder Theorem is the name of several similar theorems of abstract algebra and number theory.

Simultaneous congruences of integers

A simultaneous congruence of integers is a system of linear congruences

For all to be determined, the solution of all congruences simultaneously. If a solution exists, then lcm with the numbers exactly all solutions. However, it may also be that there is no solution.

Divider strangers modules

Derivation

The original form of the Chinese remainder theorem comes from the book Sun Zǐ Suànjīng (Chinese孙子 算 经/孙子 算 经, Sun Zi's manual of arithmetic ') of the mathematician Sun Zi ( probably 3rd century ) and 1247 of Qin Shushu Jiushaos Jiǔzhāng (数 书 九章/数 书 九章, Mathematical treatise in nine Chapters ') re-released. The set makes a statement about simultaneous congruences for the case that the moduli are relatively prime. It reads:

Be pairwise relatively prime natural numbers, then there exists for each tuple of integers is an integer that satisfies the following simultaneous congruence:

All solutions of this congruence are congruent modulo.

The product is in agreement here because of the relatively prime with the LCM.

Find a solution

A solution can be determined as follows: For each, the numbers and relatively prime, so you can for example using the extended Euclidean algorithm find two numbers and so

Set, then applies

The number

Is a solution of the simultaneous congruence.

Example

Wanted is an integer with the property

Here is. Using the extended Euclidean algorithm, we can calculate

A solution is then. Because all other solutions are therefore congruent to 47 modulo 60

General case

In the event that the modules are not relatively prime, and sometimes there is a solution. The exact condition is as follows: A solution of simultaneous congruence exists if and only if for all:

All solutions are then congruent modulo the least common multiple of.

A simultaneous congruence can in the case of existence of a solution such as solved by means of successive substitution, even if the modules are not relatively prime.

Example

A classic puzzle is to find the smallest natural number, each of the rest of can 1 when divided by 2, 3, 4, 5 and 6, and is divisible by 7. So Wanted is the smallest positive solution of the simultaneous congruence

Since the moduli are not relatively prime, one can not directly apply the Chinese remainder theorem ( with solution method ). One can but the first five conditions summarized to, ie to find a solution of

This Kongruenzsystem is now solved with the Chinese remainder theorem.

Direct solving simultaneous congruences of integers

Where are the two simultaneous congruences:

If they are solved, i.e., they are equivalent to the simple congruence:

With

This also works with non- prime numbers n and m and thus represents a significant alleviation in the solving simultaneous congruences dar.

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

Statement for principal ideal rings

Be a principal ideal ring, then is the Chinese Remainder Theorem for as follows:

Are pairwise coprime and their product, then the factor ring isomorphic to the product ring by the isomorphism

Statement for general rings

One of the most common forms of the Chinese remainder theorem is a formulation for an arbitrary ring ( with unit element ).

Are ( two-sided ) ideals, so that for ( called the ideals then prime or koprim ), and is the average of the ideals, then the factor ring isomorphic to the product ring by the isomorphism

( Is equal to the product which, if a commutative ring. )