Chinese remainder theorem Guide, Meaning , Facts, Information and Description

Simultaneous congruences of integers

The original form of the theorem, contained in a book by the Chinese mathematician Qin Jiushao published in 1247, is a statement about simultaneous congruences (see modular arithmetic). Suppose n₁, ..., n_k are positive integers which are pairwise coprime (meaning gcd (n_i, n_j) = 1 whenever i ≠ j). Then, for any given integers a₁, ..., a_k, there exists an integer x solving the system of simultaneous congruences

x_solves_it=true;
for(i= 1; i <= k; i++)
   if(x % n[i] != a[i] % n[i])
      x_solves_it=false;

A solution x can be found as follows. For each i, the integers n_i and n/n_i are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r n_i + s n/n_i = 1. If we set e_i = s n/n_i, then we have

for (i= 1; i <= k; i++)
  {r, s}= ExtendedEuclid( n[i], n / n[i] );
  e[i]= s * n / n[i];
  for(j= 1; j <= k; j++)
    if (j != i)
      assert( e[i] % n[i] 
1 && e[i] % n[j]
 0 );

for(i= 1; i <= k; i++)
  x += a[i] * e[i];

 x % 3 == 2 % 3 &&
 x % 4 == 3 % 4 &&
 x % 5 == 2 % 5

Sometimes, the simultaneous congruences can be solved even if the n_i's (n[i]'s) are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if a_i ≡ a_j (mod gcd(n_i, n_j)) (a[i] == a[j] % gcd(n[i], n[j]) for all i and j. All solutions x are congruent modulo the least common multiple of the n_i (n[i]).

Using the method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.

Statement for principal ideal domains

For a principal ideal domain R the Chinese remainder theorem takes the following form: If u₁, ..., u_k are elements of R which are pairwise coprime, and u denotes the product u₁...u_k, then the ring R/uR and the product ring R/u₁R x ... x R/u_kR are isomorphic via the isomorphism

One of the most general forms of the Chinese remainder theorem can be formulated for rings and (two-sided) ideals. If R is a ring and I₁, ..., I_k are ideals of R which are pairwise coprime (meaning that I_i + I_j = R whenever i ≠ j), then the product I of these ideals is equal to their intersection, and the ring R/I is isomorphic to the product ring R/I₁ x R/I₂ x ... x R/I_k via the isomorphism

• Chinese remainder theorem

This is an Article on Chinese remainder theorem. Page Contains Information, Facts Details or Explanation Guide About Chinese remainder theorem

	Web www.E-paranoids.com