Chinese Remainder Theorem

    When solving a linear congruence with a large moduli it is sometimes useful to reduce the linear congruence to a system of linear congruences with smaller moduli.

Proposition (Chinese Remainder Theorem) Suppose chinese remainder theorem _gr_1.gif] chinese remainder theorem _gr_2.gif] ..., chinese remainder theorem _gr_3.gif] are pairwise relatively prime positive integers. Then the system of congruences  

chinese remainder theorem _gr_4.gif]

has a unique solution modulo chinese remainder theorem _gr_5.gif]

    Proof. Let chinese remainder theorem _gr_6.gif] We know that chinese remainder theorem _gr_7.gif] for chinese remainder theorem _gr_8.gif] because chinese remainder theorem _gr_9.gif] whenever chinese remainder theorem _gr_10.gif] Therefore, for each chinese remainder theorem _gr_11.gif] there are integers chinese remainder theorem _gr_12.gif] and chinese remainder theorem _gr_13.gif] such that chinese remainder theorem _gr_14.gif] and using these chinese remainder theorem _gr_15.gif] we can construct a solution to the system as

chinese remainder theorem _gr_16.gif]

To verify this is a solution, check the chinese remainder theorem _gr_17.gif] congruence equation, namely,  

chinese remainder theorem _gr_18.gif]

If chinese remainder theorem _gr_19.gif] is a solution to the system of congruences, then chinese remainder theorem _gr_20.gif] Hence, chinese remainder theorem _gr_21.gif] for each chinese remainder theorem _gr_22.gif] and since no two of the chinese remainder theorem _gr_23.gif] have a common factor, chinese remainder theorem _gr_24.gif] that is chinese remainder theorem _gr_25.gif] Thus, chinese remainder theorem _gr_26.gif] chinese remainder theorem _gr_27.gif]

Example (Chinese Remainder Theorem) Solve the linear system of congruences

chinese remainder theorem _gr_28.gif]

    Solution. Since chinese remainder theorem _gr_29.gif] chinese remainder theorem _gr_30.gif] and chinese remainder theorem _gr_31.gif] we find integers chinese remainder theorem _gr_32.gif] and chinese remainder theorem _gr_33.gif] such that chinese remainder theorem _gr_34.gif] We find chinese remainder theorem _gr_35.gif] and chinese remainder theorem _gr_36.gif] since chinese remainder theorem _gr_37.gif] Therefore, we use
    
chinese remainder theorem _gr_38.gif]
     chinese remainder theorem _gr_39.gif]
Therefore, chinese remainder theorem _gr_40.gif] is the solution to the systems of congruence equations. chinese remainder theorem _gr_41.gif]

Example (Chinese Remainder Theorem) Solve the linear system of congruences

chinese remainder theorem _gr_42.gif]

    Solution. We find chinese remainder theorem _gr_43.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_44.gif]

So the solution is chinese remainder theorem _gr_45.gif] chinese remainder theorem _gr_46.gif]

Example (Chinese Remainder Theorem) Solve the linear system of congruences

chinese remainder theorem _gr_47.gif]

    Solution. We find chinese remainder theorem _gr_48.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_49.gif]

So the solution is chinese remainder theorem _gr_50.gif] chinese remainder theorem _gr_51.gif]

Example (Chinese Remainder Theorem) Solve the linear system of congruences

chinese remainder theorem _gr_52.gif]

    Solution. We find chinese remainder theorem _gr_53.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_54.gif]

So the solution is chinese remainder theorem _gr_55.gif] chinese remainder theorem _gr_56.gif]

Example (Chinese Remainder Theorem) Solve the linear system of congruences

chinese remainder theorem _gr_57.gif]

    Solution. We find chinese remainder theorem _gr_58.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_59.gif]

So the solution is chinese remainder theorem _gr_60.gif] chinese remainder theorem _gr_61.gif]

Proposition (Chinese Remainder Theorem) Suppose chinese remainder theorem _gr_62.gif] chinese remainder theorem _gr_63.gif] ..., chinese remainder theorem _gr_64.gif] are relatively prime positive integers and that chinese remainder theorem _gr_65.gif] for each chinese remainder theorem _gr_66.gif] Then the system of congruences  

chinese remainder theorem _gr_67.gif]

has a unique solution modulo chinese remainder theorem _gr_68.gif]

    Proof. Since chinese remainder theorem _gr_69.gif] for each chinese remainder theorem _gr_70.gif] we know that each congruence in the system has a solution, we first choose integers chinese remainder theorem _gr_71.gif] such that chinese remainder theorem _gr_72.gif] Let chinese remainder theorem _gr_73.gif] and since no two of the chinese remainder theorem _gr_74.gif] have a common factor, we see that chinese remainder theorem _gr_75.gif] Thus there is integer chinese remainder theorem _gr_76.gif] such that chinese remainder theorem _gr_77.gif] We now show that the number chinese remainder theorem _gr_78.gif] defined by  
    
chinese remainder theorem _gr_79.gif]

is a solution of the original system of congruences. First note that chinese remainder theorem _gr_80.gif] divides each chinese remainder theorem _gr_81.gif] when chinese remainder theorem _gr_82.gif] Thus for each chinese remainder theorem _gr_83.gif] we have,

chinese remainder theorem _gr_84.gif]

Hence, chinese remainder theorem _gr_85.gif] is s solution of each congruence.
    If chinese remainder theorem _gr_86.gif] is a solution to the system of congruences, then chinese remainder theorem _gr_87.gif] Hence, chinese remainder theorem _gr_88.gif] for each chinese remainder theorem _gr_89.gif] and since no two of the chinese remainder theorem _gr_90.gif] have a common factor, chinese remainder theorem _gr_91.gif] that is chinese remainder theorem _gr_92.gif] Thus, chinese remainder theorem _gr_93.gif] chinese remainder theorem _gr_94.gif]

Example (Chinese Remainder Theorem) Solve the linear systems of congruences

chinese remainder theorem _gr_95.gif]

    Solution. We find chinese remainder theorem _gr_96.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_97.gif]
The solution is   
    
chinese remainder theorem _gr_98.gif]

chinese remainder theorem _gr_99.gif]

    Linear Congruence Reduction. Let chinese remainder theorem _gr_100.gif] be the unique factorization of chinese remainder theorem _gr_101.gif] Then the linear congruence chinese remainder theorem _gr_102.gif] has the same set of solutions as the system of simultaneous congruences

chinese remainder theorem _gr_103.gif]

    As consequence of the fundamental theorem of arithmetic, chinese remainder theorem _gr_104.gif] if and only if chinese remainder theorem _gr_105.gif] for each chinese remainder theorem _gr_106.gif] This follows easily since, for some integer chinese remainder theorem _gr_107.gif]
    
chinese remainder theorem _gr_108.gif]

for each chinese remainder theorem _gr_109.gif] Hence, chinese remainder theorem _gr_110.gif] if and only if all of the congruences
    
chinese remainder theorem _gr_111.gif]

also hold. It follows that

chinese remainder theorem _gr_112.gif]

has the same set of solutions as the system of simultaneous congruences

chinese remainder theorem _gr_113.gif].
chinese remainder theorem _gr_114.gif]

Example (Chinese Remainder Theorem) Solve the linear congruence chinese remainder theorem _gr_115.gif]

    Solution. Since chinese remainder theorem _gr_116.gif] this congruence may be replaced by the system
    
chinese remainder theorem _gr_117.gif]

We find chinese remainder theorem _gr_118.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_119.gif]
The solution is   
    
chinese remainder theorem _gr_120.gif]

chinese remainder theorem _gr_121.gif]

Example (Linear Congruence Reduction) Solve the congruence chinese remainder theorem _gr_122.gif]

    Solution. Since chinese remainder theorem _gr_123.gif] this congruence may be replaced by the system
    
chinese remainder theorem _gr_124.gif]

We find chinese remainder theorem _gr_125.gif] and we use a table to construct the solution.

chinese remainder theorem _gr_126.gif]
The solution is   
    
chinese remainder theorem _gr_127.gif]

chinese remainder theorem _gr_128.gif]

Cite this as:
Chinese Remainder Theorem
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/chinese-remainder-theorem.html
 
    
Library of Math
Library of Math
Online Math Organized by Subject Into Topics
math search
Library of Math AddThis Feed Button
Online Math
Math Books
Custom math gifts on sale now.
Share your enthusiasm for mathematics!
Math Teachers
Math Gifts
The Library of Math - Online Math Organized by Subject Into Topics.
© 2005 - 2008 www.LibraryOfMath.com All rights reserved.
about us | feedback | privacy policy | terms of use | mision statement | help

Page copy protected against web site content infringement by Copyscape Valid CSS! Valid HTML 4.01 Transitional Subscribe to the Library of Math Feed
Art & Photography Shop | Being Healthy Shop | Best Sports Mall | Cafe Food Lover | Cafe Gift Shop | Cafe Internet Shop | Career Archives | City Annals
Countries Shop | Crazy Kids World | Dallas Cowboys Football Shop | Headline News Shop | Heart Boutique | Lover of Pets | Military Support Store
Musical Boutique | Online Math Store | Political Ramblings | Shop by Auction | Shop of Learning | Shop of Technology | Shop of Travels | Special Occasion Shop
Store of Hobbies | Theology Store | USA States Shop | Your Animal Store | Your Fitness World | Your Funny Store | Your Science Store