Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Chinese Remainder Theorem"

(→‎See Also)
(→‎Extended version of the theorem)
Line 6: Line 6:
  
 
'''General Case''': the proof of the general case follows by induction to the above result (k-1) times.
 
'''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 <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 extended version).
 

Revision as of 18:12, 19 January 2016

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.

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 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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Chinese_Remainder_Theorem&oldid=74711"