# Chinese Remainder Theorem Tutorial

Page 1 of 1

## 0 Replies - 24059 Views - Last Post: 03 July 2011 - 07:17 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=238017&amp;s=28f8e340da289c3acf42f724e75867e0&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11344
• Posts: 42,784
• Joined: 27-December 08

# Chinese Remainder Theorem Tutorial

Posted 03 July 2011 - 07:17 PM

This tutorial is the second part to my earlier tutorial on modular arithmetic and the Euclidean algorithm. It will cover the Chinese Remainder Theorem.

Chinese Remainder Theorem
The Chinese Remainder Theorem is used to solve a series of modular equations.
x = a1 (mod n1)
x = a2 (mod n2)
x = a3 (mod n3)
x = ax (mod nx)

The first step is to ensure all the terms are coprime, or relatively prime. This means that two numbers share no other positive factors than 1. In other words, two numbers are coprime if their greatest common factor is 1. If they are not coprime, then it is necessary to factor the moduli based on the highest power of their greatest common prime factor. The powers of the prime factor do not have to be the same for all the moduli. One of two things will happen at this point. Either the new modular congruences will be contradictory, or redundancies will exist and the congruences with the lower powers can simply be ignored.

The second step is to multiply all the modular bases n1 through nx together into a variable p. This variable p will be used later on to generate the numbers to find the modular inverse for in each term in the final equation.

The last step is to set up the general form equation, which looks like:
x = [a1(p/n1)((p/n1)-1 (mod n1)) + a2(p/n2)((p/n2)-1 (mod n2)) + ... ax(p/nx)((p/nx)-1 (mod nx)) ] (mod p)

Let's work through a couple examples. The first one is:
x = 3 (mod 12)
x = 7 (mod 54)

Both 12 and 54 have a common prime factor of 3. The greatest power of 3 that divides 12 is 31, and the greatest power of 3 that divides 54 is 33. Factoring these moduli produces the following set of congruences:
x = 3 (mod 4)
x = 3 (mod 3) = 0 (mod 3)
x = 7 (mod 2) = 1 (mod 2)
x = 7 (mod 27)

Since x = 0 (mod 3) and x = 7 (mod 27) are contradictory, there is no solution for this problem.

The second problem is as follows:
x = 7 (mod 200)
x = 82 (mod 375)

Both 200 and 375 share the prime factor 5. Using that, the congruences can be broken down to:
x = 7 (mod 25)
x = 7 (mod 8)
x = 82 (mod 125)
x = 82 (mod 3) = 1 (mod 3)

Since 25 and 125 are both powers of 5 and are equivalent, x = 82 (mod 125) remains while x = 7 (mod 25) can be ignored, leaving:
x = 7 (mod 8)
x = 82 (mod 125)
x = 1 (mod 3)

Now let's calculate p, which is the product of the moduli. So p = 8(125)(3) = 3000.

The final step is to set up the final congruence:
x = [7(3000/8)[(3000/8)-1 (mod 8)] +
82(24)(24-1 (mod 125)) +
1000(1000-1 (mod 3))
(mod 3000)]

This can be simplified to:
x = [7(7)(375) + 82(24)(99) + 1000(1)(1)] (mod 3000)

x = [18375 + 194832 + 1000] (mod 3000)
x = [375 + 2832 + 1000] (mod 3000)
x = 4207 (mod 3000)
x = 1207 (mod 3000)

Now let's check 1207 against the initial congruences:
x = 7 (mod 200)
x = 82 (mod 375)

Both of these congruences are satisfied by the solution x = 1207 (mod 3000). So 1207 is a valid solution, but there are many more solutions that are also valid so long as they come out to 1207 when the (mod 3000) operation is applied.

Is This A Good Question/Topic? 2

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }