[SC] Extra. Chinese Remainder Theorem

Congruence

To begin, a congruence is a therm used to designate two different integers that have the same remainder when they are divided by a natural number.

Mathematical Definition

"Given a, b and m, with m > 0 that belongs to the set of integers, we say that a is congruent to b mod m if m divides
exactly (a-b).
a and b are congruent module m if and only if a and b have the same residue to be divided by m, individually.

a ≡ b (mod m)

m | (a - b)

The expression is read "a is congruent to b module m" and m is considered the module of the congruence.

P.E:

• 27 ≡ 3 (mod 4), because (27 - 3) = 24, is divisible by 4 with remainder 0
• 47 ≡ 7 (mod 8), because (47 - 4) = 44, is divisible by 8 with remainder 0
• 1 ≡ -1 (mod 2), because (1 - (-1)) = 2, is divisible by 2 with remainder 0

Properties

The congruences have 3 properties:

• Reflexive:
  a ≡ a (mod m)
• Symmetric:
  IF a ≡ b (mod m) ⇒ b ≡ a (mod m)
• Transitive:
  IF a ≡ b (mod m) ∧ b ≡ c (mod m) ⇒ a ≡ c (mod m)

**NOTE: If you want to know more, please see the references at the final of the end of this post

Chinese Remainder Theorem

The Chinese Remainder Theorem is a method used in number theory to solve systems of congruences.

A system with 2 or more lineal congruences don't have necessary a solution, even if each individual congruence have one. A system of lineal congruences is denoted by:

b1x ≡ a1 (mod m1)

b2x ≡ a2 (mod m2)
bix ≡ ai (mod mi)

But, all system with 2 or more lineal congruences which individualy accepts a unique solution, also accepts a simultaneous solution if the modules are comprimes with each other.

The chinese mathematician Sun Tsu Suan-Ching pose the following problem around the 4th century b.C:

"There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?"

Problems of this kind are all examples known as the Chinese Remainder Theorem. In mathematical words the problems can be solved finding n, given its remainders of division by several numbers m1, m2, ..., mk.

Mathematical Definition

Suppose that m1, m2, ..., mk are positive integers, relatively primes each other in pairs (mi, mk) = 1, if i ≠ k. And b1, b2, ..., bk are arbitrary integers. In the system of lineal congruences:

x ≡ b1 (mod m1)

x ≡ b2 (mod m2)
...

x ≡ bk (mod mk)

All the solutions of x are congruent module m, with m = m1 * m2 * ... * mk

Proof

M = m1 * m2 * ... * mk
Mk = M/mk

So, if all the modules are taken in pairs, and they are comprimes with each other, that means that gcd(Mk, mk) = 1, applying the rule gcd(a, m) = d, then, the congruency ax ≡ b (mod m) have a solution if, and only if d | b.

Now, x = b1*M1*y1 + b2*M2*y2 + ... + bk*Mk*yk

If we considerate each term of this summatory a module of mk.
Given that Mi ≡ 0 (mod mk), if i ≠ k, we have that x ≡ bk*Mk*yk ≡ bk (mod mk).

This means that x satisfies each one of the congruences of the system

By the symetric property, if x and b are two solutions of the system, we have that x ≡ b (mod mk) for each k. And because each mk are relatively primes each other by pairs, we also have that x ≡ b (mod M).

Example

"Find the two minimal prime numbers that have remainders 2,3,2 when they are divided by 3,5 and 7 respectively.

Solution

The system can be modeled in a system of congruences:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

The solution starts:

m = 3*5*7 = 105

Then:

M1 = m/3 = 105/3 = 35
M2 = m/5 = 105/5 = 21
M3 = m/7 = 105/7 = 15

Next:

y1 = M1 (mod 3) = 35 (mod 3) = 2
y2 = M2 (mod 5) = 21 (mod 5) = 1
y3 = M3 (mod 7) = 15 (mod 7) = 1

Now, find x:

x = b1*M1*y1 + b2*M2*y2 + b3*M3*y3
x = 2*35*2 + 3*21*1 + 2*15*1
x = 140 + 63 + 30
x = 233

Now we have 233 ≡ y mod(105)

Applying the symmetry rule

y ≡ 233 mod(105)
233 mod(105) = 23

The solution is 233 ≡ 23 mod(105), and 2 minimal integers could be 23 and 233, but, if we divide (233-23)/105, the result is 2, maybe there are another number where the result is one.

1 = (x-23)/105 also 1 = 105/105

Then

105+23 = 128 and 1 = (128-23)/105

The 2 minimal integers are 23 and 128.



References

• http://mat.izt.uam.mx/notas_de_clase/congruencias.pdf
• http://www.scribd.com/doc/43526801/Teorema-Chino-de-los-Restos
• http://www.cut-the-knot.org/blue/chinese.shtml
• http://www.millersville.edu/~bikenaga/number-theory/chinese-remainder/chinese-remainder.pdf
• http://www.mat.upm.es/~pzz/docencia/grado/mtds/congruencias_sin_pause4.pdf
• http://www.trans4mind.com/personal_development/mathematics/numberTheory/chineseRemainderTheoremFormula2.htm
• Google Books | Number Theory: Congruences (Spanish)