Difference between revisions of "Chinese Remainder Theorem"

Revision as of 16:59, 25 December 2007

The Chinese Remainder Theorem is a number theoretic result.

History

When the ancient Chinese army was at its peak, it was said that the emperor developed a way to count the soldiers. Rather than count his hordes one man at a time, he developed a system. He would have his soldiers divide into groups of 3, and count the men who didn't have a group. He would then do groups of 5, etc. Eventually, using these remainders, he could calculate the size of his army using a technique we now call the Chinese Remainder Theorem.

Proof

If $a \equiv b \pmod{mn}$ , then $a$ and $b$ clearly differ by a multiple of $mn$ , so $a \equiv b \pmod{m}$ and $a \equiv b \pmod{n}$ . This is the first part of the theorem. The converse follows because $a$ and $b$ must differ by a multiple of $m$ and $n$ , and $\mbox{lcm}(m,n) = mn$ . This is the second part of the theorem.

Applicability

Much like the Fundamental Theorem of Arithmetic, many people seem to take this theorem for granted before they consciously turn their attention to it. It ubiquity derives from the fact that many results can be easily proven mod (a power of a prime), and can then be generalized to mod $m$ using the Chinese Remainder Theorem. For intance, Fermat's Little Theorem may be generalized to the Fermat-Euler Theorem in this manner. Its application in problem-solving is similar.

General Case: the proof of the general case follows by repeatedly applying to above result (k-1) times.

Extended version of the theorem

Suppose one tried to divide a group of objects into $2$ , $3$ and $4$ parts instead and found $1$ , $1$ and $2$ fish left over, respectively. One can show this to be impossible, because any number giving remainder $1$ modulo $2$ must be odd and any number giving remainder $2$ modulo $4$ must be even. Thus, the number of objects must be odd and even simultaneously, which is absurd. Thus, there must be some restrictions on the numbers $a_1,\dots,a_n$ to ensure that at least one solution exists. It turns out (and this is the extended version of the theorem) that

The solution exists if and only if $a_i\equiv a_j\mod \gcd(m_i,m_j)$ for all $i,j$ where $\gcd$ stands for the greatest common divisor. Moreover, in the case when the problem is solvable, any two solutions differ by some common multiple of $m_1,\ldots,m_n$ .

Discussion

Here is an AoPS thread in which the Chinese Remainder Theorem is discussed and implemented.

@@ Line 1: / Line 1: @@
-The '''Chinese Remainder Theorem''' is a [[number theory | number theoretic]] result.  As it can be applied to problems with a very wide range of difficulty, this article was split into the following two articles:
+The '''Chinese Remainder Theorem''' is a [[number theory | number theoretic]] result.
-* [[Chinese Remainder Theorem/Introductory]]
+==History==
-* [[Chinese Remainder Theorem/Advanced]]
+When the ancient Chinese army was at its peak, it was said that the emperor developed a way to count the soldiers.  Rather than count his hordes one man at a time, he developed a system.  He would have his soldiers divide into groups of 3, and count the men who didn't have a group.  He would then do groups of 5, etc.  Eventually, using these remainders, he could calculate the size of his army using a technique we now call the Chinese Remainder Theorem.
+== Proof ==
+If <math>a \equiv b \pmod{mn}</math>, then <math>a</math> and <math>b</math> clearly differ by a multiple of <math>mn</math>, so <math>a \equiv b \pmod{m}</math> and <math>a \equiv b \pmod{n}</math>.  This is the first part of the theorem.  The converse follows because <math>a</math> and <math>b</math> must differ by a multiple of <math>m</math> and <math>n</math>, and <math>\mbox{lcm}(m,n) = mn</math>.  This is the second part of the theorem.
+== Applicability ==
+Much like the [[Fundamental Theorem of Arithmetic]], many people seem to take this theorem for granted before they consciously turn their attention to it.  It ubiquity derives from the fact that many results can be easily proven mod (a power of a prime), and can then be generalized to mod <math>m</math> using the Chinese Remainder Theorem.  For intance, [[Fermat's Little Theorem]] may be generalized to the [[Fermat-Euler Theorem]] in this manner.  Its application in [[problem-solving]] is similar.
+'''General Case''': the proof of the general case follows by repeatedly applying to above result (k-1) times.
+==Extended version of the theorem==
+Suppose one tried to divide a group of objects into <math>2</math>, <math>3</math> and <math>4</math> parts instead and found <math>1</math>, <math>1</math> and <math>2</math> fish left over, respectively. One can show this to be impossible, because any number giving remainder <math>1</math> modulo <math>2</math> must be [[odd integer | odd]] and any number giving remainder <math>2</math> modulo <math>4</math> must be [[even integer | even]]. Thus, the number of objects must be odd and even simultaneously, which is absurd. Thus, there must be some restrictions on the numbers <math>a_1,\dots,a_n</math> to ensure that at least one solution exists.  It turns out (and this is the extended version of the theorem) that
+''The solution exists if and only if <math>a_i\equiv a_j\mod \gcd(m_i,m_j)</math> for all <math>i,j</math> where <math>\gcd</math> stands for the [[greatest common divisor]]. Moreover, in the case when the problem is solvable, any two solutions differ by some [[common multiple]] of <math>m_1,\ldots,m_n</math>.''
+==Discussion==
+* [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=80124&sid=df9439496046e0ff9f97cfc644408395 Here] is an AoPS thread in which the Chinese Remainder Theorem is discussed and implemented.
+[[Category:Number theory]]

Page

Toolbox

Search