Library of Math
Library of Math
Online Math Organized by Subject Into Topics
Subscribe to the Library of Math Feed
  Math Online Math Books Math Gifts Math Auctions  
PRINT LINKED RELATED

Chinese Remainder Theorem Example

    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.

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

chinese remainder theorem example _gr_4.gif]

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

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

chinese remainder theorem example _gr_6.gif]

    Solution. Since chinese remainder theorem example _gr_7.gif] chinese remainder theorem example _gr_8.gif] and chinese remainder theorem example _gr_9.gif] we find integers chinese remainder theorem example _gr_10.gif] and chinese remainder theorem example _gr_11.gif] such that chinese remainder theorem example _gr_12.gif] We find chinese remainder theorem example _gr_13.gif] and chinese remainder theorem example _gr_14.gif] since chinese remainder theorem example _gr_15.gif] Therefore, we use
    
chinese remainder theorem example _gr_16.gif]
     chinese remainder theorem example _gr_17.gif]
Therefore, chinese remainder theorem example _gr_18.gif] is the solution to the systems of congruence equations. chinese remainder theorem example _gr_19.gif]

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

chinese remainder theorem example _gr_20.gif]

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

chinese remainder theorem example _gr_22.gif]

So the solution is chinese remainder theorem example _gr_23.gif] chinese remainder theorem example _gr_24.gif]

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

chinese remainder theorem example _gr_25.gif]

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

chinese remainder theorem example _gr_27.gif]

So the solution is chinese remainder theorem example _gr_28.gif] chinese remainder theorem example _gr_29.gif]

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

chinese remainder theorem example _gr_30.gif]

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

chinese remainder theorem example _gr_32.gif]

So the solution is chinese remainder theorem example _gr_33.gif] chinese remainder theorem example _gr_34.gif]

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

chinese remainder theorem example _gr_35.gif]

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

chinese remainder theorem example _gr_37.gif]

So the solution is chinese remainder theorem example _gr_38.gif] chinese remainder theorem example _gr_39.gif]

(7) Proposition (Chinese Remainder Theorem) Suppose chinese remainder theorem example _gr_40.gif] chinese remainder theorem example _gr_41.gif] ..., chinese remainder theorem example _gr_42.gif] are relatively prime positive integers and that chinese remainder theorem example _gr_43.gif] for each chinese remainder theorem example _gr_44.gif] Then the system of congruences  

chinese remainder theorem example _gr_45.gif]

has a unique solution modulo chinese remainder theorem example _gr_46.gif]

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

chinese remainder theorem example _gr_47.gif]

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

chinese remainder theorem example _gr_49.gif]
The solution is   
    
chinese remainder theorem example _gr_50.gif]

chinese remainder theorem example _gr_51.gif]

    Linear Congruence Reduction. Let chinese remainder theorem example _gr_52.gif] be the unique factorization of chinese remainder theorem example _gr_53.gif] Then the linear congruence chinese remainder theorem example _gr_54.gif] has the same set of solutions as the system of simultaneous congruences

chinese remainder theorem example _gr_55.gif]

    As consequence of the fundamental theorem of arithmetic, chinese remainder theorem example _gr_56.gif] if and only if chinese remainder theorem example _gr_57.gif] for each chinese remainder theorem example _gr_58.gif] This follows easily since, for some integer chinese remainder theorem example _gr_59.gif]
    
chinese remainder theorem example _gr_60.gif]

for each chinese remainder theorem example _gr_61.gif] Hence, chinese remainder theorem example _gr_62.gif] if and only if all of the congruences
    
chinese remainder theorem example _gr_63.gif]

also hold. It follows that

chinese remainder theorem example _gr_64.gif]

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

chinese remainder theorem example _gr_65.gif].
chinese remainder theorem example _gr_66.gif]

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

    Solution. Since chinese remainder theorem example _gr_68.gif] this congruence may be replaced by the system
    
chinese remainder theorem example _gr_69.gif]

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

chinese remainder theorem example _gr_71.gif]
The solution is   
    
chinese remainder theorem example _gr_72.gif]

chinese remainder theorem example _gr_73.gif]

(10) Example (Linear Congruence Reduction) Solve the congruence chinese remainder theorem example _gr_74.gif]

    Solution. Since chinese remainder theorem example _gr_75.gif] this congruence may be replaced by the system
    
chinese remainder theorem example _gr_76.gif]

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

chinese remainder theorem example _gr_78.gif]
The solution is   
    
chinese remainder theorem example _gr_79.gif]

chinese remainder theorem example _gr_80.gif]

Number Theory Books

A Beginner's Guide to Constructing the Universe: Mathematical Archetypes of N... Product Image
List Price: $18.95
Buy New: $10.98
You Save: $7.97 (42%)
New (31) Used (24) from $7.58The Universe May Be a Mystery,But It's No SecretMichael Schneider leads us on a spectacular, lavishly illustrated journey along the numbers one through ten to explore the mathematical principles made visible (more)
Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... Product Image
List Price: $16.00
Buy New: $8.86
You Save: $7.14 (45%)
New (38) Used (19) from $7.49In 1859, Bernhard Riemann, a little-known thirty-two year old mathematician, made a hypothesis while presenting a paper to the Berlin Academy titled "On the Number of Prime Numbers Less Than a Given Quantity." (more)
Bayesian Computation with R (Use R) Product Image
List Price: $49.95
Buy New: $37.82
You Save: $12.13 (24%)
New (35) Used (13) from $35.75There has been a dramatic growth in the development and application of Bayesian inferential methods. Some of this growth is due to the availability of powerful simulation-based algorithms to summarize (more)
Euler's Gem: The Polyhedron Formula and the Birth of Topology Product Image
List Price: $27.95
Buy New: $16.98
You Save: $10.97 (39%)
New (32) Used (4) from $16.98Leonhard Euler's polyhedron formula describes the structure of many objects--from soccer balls and gemstones to Buckminster Fuller's buildings and giant all-carbon molecules. Yet Euler's formula is so (more)
e: The Story of a Number Product Image
List Price: $19.95
Buy Used: $2.94
You Save: $17.01 (85%)
New (11) Used (38) Collectible (1) from $2.94The interest earned on a bank account, the arrangement of seeds in a sunflower, and the shape of the Gateway Arch in St. Louis are all intimately connected with the mysterious number e. In this informal (more)
Not Even Wrong: The Failure of String Theory and the Search for Unity in Phys... Product Image
List Price: $16.95
Buy New: $7.61
You Save: $9.34 (55%)
New (34) Used (11) from $6.78When does physics depart the realm of testable hypothesis and come to resemble theology? Peter Woit argues that string theory isn't just going in the wrong direction, it's not even science. Not Even Wrong (more)
Killer Poker By the Numbers: Mathematical Edge for Winning Play Product Image
List Price: $14.95
Buy New: $6.99
You Save: $7.96 (53%)
New (34) Used (13) from $6.99Killer Poker By the Numbers: Mathematical Edge for Winning Play (more)
Elementary Number Theory (5th Edition) Product Image
List Price: $124.00
Buy New: $99.20
You Save: $24.80 (20%)
New (9) Used (17) from $79.05Elementary Number Theory and Its Applications is noted for its outstanding exercise sets, including basic exercises, exercises designed to help students explore key concepts, and challenging exercises. (more)
Complex Analysis for Mathematics and Engineering Product Image
List Price: $124.95
Buy New: $48.99
You Save: $75.96 (61%)
New (14) Used (15) from $47.90Revised and updated, the new Fifth Edition of Complex Analysis for Mathematics and Engineering presents a comprehensive, student-friendly introduction to Complex Analysis. It's clear, concise writing (more)
Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills Product Image
List Price: $29.95
Buy New: $14.74
You Save: $15.21 (51%)
New (43) Used (15) from $14.49I used to think math was no fun'Cause I couldn't see how it was doneNow Euler's my heroFor I now see why zeroEquals e[pi] i+1--Paul Nahin, electrical engineer In the mid-eighteenth century, Swiss-born (more)

Cite this as:
Chinese Remainder Theorem Example
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/chinese-remainder-theorem-example.html
Online Math
Math Store
about us contact us privacy policy terms of use mision statement lom help
The Library of Math - Online Math Organized by Subject Into Topics. © 2005 - 2009 www.LibraryOfMath.com All rights reserved. math rss