Difference between revisions of "Chinese Remainder Theorem"
Armalite46 (talk | contribs) |
Armalite46 (talk | contribs) (→See Also) |
||
Line 47: | Line 47: | ||
==See Also== | ==See Also== | ||
*[[Modular arithmetic/Introduction]] | *[[Modular arithmetic/Introduction]] | ||
+ | *[[Chicken McNugget Theorem]] | ||
+ | |||
==Discussion== | ==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. | * [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. |
Revision as of 12:01, 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
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:
and no have any divisors in common for
.
Let
, and
.
Now if the numbers
satisfy:
for every , then a solution for
is:
Proof
If , then
and
clearly 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. 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 fish into ,
and
parts instead and found
,
and
fish left over, respectively. One can show this to be impossible, because any number giving remainder
modulo
must be odd and any number giving remainder
modulo
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
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 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
.
See Also
Discussion
- Here is an AoPS thread in which the Chinese Remainder Theorem is discussed and implemented.