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  

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.45
You Save: $8.50 (45%)
New (37) Used (28) from $8.49The 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)
Bayesian Computation with R (Use R) Product Image
List Price: $49.95
Buy New: $33.51
You Save: $16.44 (33%)
New (32) Used (8) from $33.51There 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)
e: The Story of a Number Product Image
List Price: $19.95
Buy New: $8.23
You Save: $11.72 (59%)
New (42) Used (32) Collectible (1) from $3.25The 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)
Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... Product Image
List Price: $16.00
Buy New: $8.91
You Save: $7.09 (44%)
New (35) Used (15) 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)
Euler's Gem: The Polyhedron Formula and the Birth of Topology Product Image
List Price: $27.95
Buy New: $17.00
You Save: $10.95 (39%)
New (27) Used (3) from $14.99Leonhard 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)
Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills Product Image
List Price: $29.95
Buy New: $17.98
You Save: $11.97 (40%)
New (36) Used (10) from $17.98I 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)
The Fabulous Fibonacci Numbers Product Image
List Price: $28.98
Buy New: $15.00
You Save: $13.98 (48%)
New (35) Used (11) Collectible (1) from $14.50The most ubiquitous, and perhaps the most intriguing, number pattern in mathematics is the Fibonacci sequence. In this simple pattern beginning with two ones, each succeeding number is the sum of the two (more)
Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) Product Image
List Price: $14.95
Buy New: $7.69
You Save: $7.26 (49%)
New (35) Used (13) from $7.69Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) (more)
Sacred Number: The Secret Quality of Quantities (Wooden Books) Product Image
List Price: $12.00
Buy New: $5.59
You Save: $6.41 (53%)
New (30) Used (13) from $5.59Numbers permeate every aspect of our lives; very little happens without a basic ability to manipulate the simple whole numbers we all take for granted. Beautifully illustrated with old engravings as well (more)
The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics Product Image
List Price: $13.95
Buy Used: $0.98
You Save: $12.97 (93%)
New (28) Used (29) from $0.98In 1859, German mathematician Bernhard Riemann presented a paper to the Berlin Academy that would forever change the history of mathematics. The subject was the mystery of prime numbers. At the heart of (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 - 2008 www.LibraryOfMath.com All rights reserved. math rss