Difference between revisions of "Chinese Remainder Theorem"
Armalite46 (talk | contribs) (→See Also) |
Armalite46 (talk | contribs) |
||
Line 8: | Line 8: | ||
− | Simply stated | + | Simply stated: |
Suppose you wish to find the least number <math>x</math> which leaves a remainder of: | Suppose you wish to find the least number <math>x</math> which leaves a remainder of: | ||
Line 19: | Line 19: | ||
</center> | </center> | ||
− | + | such that <math>d_{1}</math> , <math>d_{2}</math> , ... <math>d_{n}</math> are all relatively prime. | |
Let <math>M = d_{1}d_{2} \cdots d_{n}</math>, and <math>b_{i} = \frac{M}{d_{i}}</math>. | Let <math>M = d_{1}d_{2} \cdots d_{n}</math>, and <math>b_{i} = \frac{M}{d_{i}}</math>. | ||
Now if the numbers <math>a_{i}</math> satisfy: | Now if the numbers <math>a_{i}</math> satisfy: | ||
Line 31: | Line 31: | ||
== Proof == | == Proof == | ||
− | If <math>a \equiv b \pmod{mn}</math>, then <math>a</math> and <math>b</math> | + | If <math>a \equiv b \pmod{mn}</math>, then <math>a</math> and <math>b</math> 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 == | == 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 instance, [[Fermat's Little Theorem]] may be generalized to the [[Fermat-Euler Theorem]] in this manner | + | 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 instance, [[Fermat's Little Theorem]] may be generalized to the [[Fermat-Euler Theorem]] in this manner. |
− | '''General Case''': the proof of the general case follows by | + | '''General Case''': the proof of the general case follows by induction to the above result (k-1) times. |
==Extended version of the theorem== | ==Extended version of the theorem== | ||
− | Suppose one tried to divide a group of fish 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. | + | Suppose one tried to divide a group of fish 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. Any number with remainder <math>1</math> mod <math>2</math> must be [[odd integer | odd]] and any number with remainder <math>2</math> mod <math>4</math> must be [[even integer | even]]. Thus, the number of objects must be odd and even simultaneously, which is a contradiction. Thus, there must be restrictions on the numbers <math>a_1,\dots,a_n</math> to ensure that at least one solution exists. It follows 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>.'' | + | ''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>.'' (the extended version). |
==See Also== | ==See Also== |
Revision as of 11:08, 6 August 2013
The Chinese Remainder Theorem is a number theoretic result. It is one of the only theorems named for an oriental person or place, due to the closed development of mathematics in the western world.
Contents
[hide]Theorem
Formally stated, the Chinese Remainder Theorem is as follows:
Let be relatively prime to . Then each residue class mod is equal to the intersection of a unique residue class mod and a unique residue class mod , and the intersection of each residue class mod with a residue class mod is a residue class mod .
Simply stated:
Suppose you wish to find the least number which leaves a remainder of:
such that , , ... are all relatively prime. Let , and . Now if the numbers satisfy:
for every , then a solution for is:
Proof
If , then and differ by a multiple of , so and . This is the first part of the theorem. The converse follows because and must differ by a multiple of and , and . 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 using the Chinese Remainder Theorem. For instance, Fermat's Little Theorem may be generalized to the Fermat-Euler Theorem in this manner.
General Case: the proof of the general case follows by induction to the above result (k-1) times.
Extended version of the theorem
Suppose one tried to divide a group of fish into , and parts instead and found , and fish left over, respectively. Any number with remainder mod must be odd and any number with remainder mod must be even. Thus, the number of objects must be odd and even simultaneously, which is a contradiction. Thus, there must be restrictions on the numbers to ensure that at least one solution exists. It follows that:
The solution exists if and only if for all where stands for the greatest common divisor. Moreover, in the case when the problem is solvable, any two solutions differ by some common multiple of . (the extended version).
See Also
Discussion
- Here is an AoPS thread in which the Chinese Remainder Theorem is discussed and implemented.