Examples based on Chinese Remainder Theorem

-


Steps to solve the system of congruences :


Step 1: Take the congruence with the largest modulus x  an (mod mn) then rearrange it as,

x=mnk+an    

where k is an integer.

Step 2: Substitute x into the 2nd largest modulus mnk+an  an-1 (mod mn-1) then solve the  congruence

k  h (mod mn-1).

Step 3: Rewrite the congruence as k= mn-1d+h and substitute it in x.

Step 4: Substitute the solve equation of x in the next largest modulus then solve the congruence.

Step 5: Repeat the above steps until the solution arrives.                   


Chinese Remainder Theorem


Examples:


  1. If you have a bowl of chocolates but the exact number is unknown and you distribute it among 3 children you have 2 leftovers, you distribute it among 5 children and have 3 leftovers, you distribute it among 7 children and have 2 leftovers. How many chocolates are there??

Soln:

 According to question,

x  2 (mod 3)

x  3 (mod 5)

x  2 (mod 7)

First, take the congruence with the largest modulus,

x  2 (mod 7)

Rewrite it as an equivalence equation,   

x=7k+2 ,for some integer k ……(1)

Substitute x into second largest modulus,

x  3 (mod 5)

      7k+2  3 (mod 5)

    7k  1 (mod 5)

By solving the linear congruence,

We get,                

k  3 (mod 5)

Rewrite it as an equivalence equation,   

k=5a+3,for some integer a

Substituting this in equation (1),

x=7(5a+3)+2

    x=35a+21+2

     x=35a+2 ...(2)

Substitute x into third largest modulus,

35a+23  2 (mod 3)

35a+21  0 (mod 3)

By solving the linear congruence,

We get,                  

a  0 (mod 3)

Rewrite it as an equivalence equation,

a=3n,for some integer n

Substituting this in equation (2),

x=35a+23

=35(3n)+23

=105n+23

Rewriting this,

x  23 (mod 105)

 Note that, M=3x5x7=105

x=23

Therefore, the number of chocolates in the bowl is 23.





 

  1. x 2 (mod 3)

     x  1 (mod 4)

     x  5 (mod 7)

Soln:


Begin with the largest modulus,

x  5 (mod 7)

Rewriting it,   

x=7k+5 ,for some integer k ……(1)

Substitute x into second largest modulus,

x  1 (mod 4)

  7k+5  1 (mod 4)

   7k+4  0 (mod 4)

Solving the congruence,

We get,                

k  0 (mod 4)

Rewriting it,   

k=4a,for some integer a

Substituting this in equation (1),

x=7(4a)+5

  x=28a+5

    x=28a+5 ...…(2)

Substitute x into third largest modulus,

28a+5 2 (mod 3)

28a+3 0 (mod 3)

Solving the congruence,

We get,                  

a  0 (mod 3)

Rewriting it,

a=3n,for some integer n

Substituting this in equation (2),

x=28a+5

=28(3n)+5

=84n+5

Rewriting this,

x  5 (mod 84)

 Here, M = 3x4x7= 84

Therefore, x=5                    



                  

 

 

 

 

 

3. There is a ship where pirates have a stolen treasure, a box full of unknown numbers of gold coins. Somehow, they figured out that the gold coins are between 70 and 90. If they plan to distribute it among 8 pirates they’ll have 6 gold coins left,  they distribute it among 7 pirates, they'll have 1 gold coin left, they distribute it among 5 pirates and they'll have 3 gold coins left. How many gold coins are there ???

Soln:

According to question,

x  3 (mod 5)

x  1 (mod 7)

x  6(mod 8)

Begin with the largest modulus,

x  6(mod 8)

Rewriting it, 

x=8k+6 ,for some integer k ……(1)

Substitute x into second largest modulus,

x  1 (mod 7)

  8k+6  1 (mod 7)

     8k+5  0 (mod 7)

Solving the congruence,

We get,                

k  2 (mod 7)

Rewriting it,   

k=7a+2,for some integer a

Substituting this in equation (1),

x=8(7a+2)+6

  x=56a+16+6

  x=56a+22 ...…(2)

Substitute x into third largest modulus,

56a+22  3 (mod 5)

56a+19  0 (mod 5)

Solving the congruence,

We get,                  

a  1 (mod 5)

Rewriting it, 

                    a=5n+1,for some integer n

Substituting this in equation (2),

x=56a+22

=56(5n+1)+22

=280n+56+22

=280n+78

Rewriting this,

x  78 (mod 280)

Note that, M = 8x5x7 = 280

x=78

Therefore, there are 78 gold coins.

 

 
Hey there, This is Hifza Siddiqui, an aspiring Mathematician pursuing masters from the University of Mumbai. I'm writing this blog to share the knowledge and the way I understand mathematics. I hope it helps you to get a better insight. My blog's frequency will be twice per week.

Comments

Post a Comment

Please do not enter spam link in the comment box

Recent blogs

Topology

-
Image
    What is topology ? What is topology used for? Topology is a branch of mathematics that deals with the properties of an object that are invariant ( do not change ) under continuous deformations like stretching, crushing, coiling. However, shredding or gluing is not allowed.  It also gives the spatial relation of the elements of a set. In simple words, two objects ( spaces ) that can be deformed into each other are topologically isomorphic.   cube turning into dodecahedron by  Tomruen   For example,   A cube can be deformed into a sphere without breaking it, square into a circle, coffee cup into a torus ( doughnut) , double doughnut into a kettle, and scissor.  Fun Fact: It is said that topologists cannot distinguish between a coffee mug and a doughnut. Types of Topology Applications of topology: In mathematics: It is used in various fields of mathematics such as number theory, differential equations, dynamical systems, knot theory and Ri...
Read more

Integration = Area under the curve?

-
Image
What is the concept of integration ?  What is the purpose of integration ?  Why does integrating give you area under the curve? Integration, also known as  anti-derivative   of a function, gives the area under the curve of the function.  Most of you already know all this thing but did  you  ever wonder  why integration gives you area under the curve?  How does it work actually? Well, the answer is quite simple and basic. We will take some polynomials as examples and the integration rule for a polynomial term of an arbitrary degree n " $ax^n $  " is given by \[\int ax^n dx=\frac{ax^{n+1}}{n+1}+C\]
Read more

Types of Topology

-
Image
Types of Topology        General or point-set Topology: It generalizes the basic concepts such as connectedness, continuity, compactness by using definitions from set theory and lays the foundation for the other branches. Changing the topology can change which functions are continuous and which subsets are connected or compact. Topological spaces have metric spaces as an important class as they simplify many proofs.           Algebraic Topology: It associates the algebraic objects with topology . In this algebraic structures are used as tools to study the variations of geometric objects. The basic idea is to consider two spaces to be identical if they have the same shape. Sometimes, the topologically isomorphic shapes seem different geometrically, like a cuboid and sphere but their algebraic properties are similar, so it becomes easier to study it by converting these problems to algebraic ones.     It gives the con...
Read more

Chinese Remainder Theorem

-
How do you solve Chinese Remainder Theorem? How do you solve a system of congruence? How can CRT be used to speed up RSA decryption? Chinese Remainder Theorem (C.R.T) , given by Sun Zi, is one of the brilliant concepts in mathematics, it represents Horace's quote beautifully,  omne tulit punctum qui miscuit utile dulci (he gains everyone’s approval who mixes the pleasant with the useful).   In number theory, the C.R.T . gives us the unique remainder from the simultaneous linear congruences by solving the congruences using th e Euclidean division where the divisors are coprime. Statement: If we take t number of integers a 1 ,a 2 ,a 3 ,…,a t  and m 1 ,m 2 ,m 3 ,…,m t  be coprime (i.e gcd of two numbers is 1) then there is a number x with the property that,   x  º  a i  (mod m i )     1  £  i  £  t      .......(1) The number x is unique in the following sense:   Let M be the product of all ...
Read more

Riemann Sums and Integral

-
Image
Riemann sums and Integral was introduced by a German Mathematician Bernhard Riemann . What are Riemann sums?  How do you convert integrals to Riemann sums?  How do you calculate Riemann integral ?  Its argument arose when we want to find the area under the curve of a function. Imagine that you are given a rectangle or any other polygon or a function how will you calculate the area under the curve ?    Riemann sums (RS) is there to help you. I t is used to approximate the area under the curve of a function by adding shapes like rectangle, trapezoid, etc . But the question here is how can we make these rectangles? There are three choices when it comes to making rectangles to approximate the area.
Read more

Complete proof of Chinese Remainder Theorem

-
Image
Statement: If we take t number of integers a 1 ,a 2 ,a 3 ,…,a t   and   m 1 ,m 2 ,m 3 ,…,m t   be coprime (i.e gcd of two numbers is 1) then there is a number x with the property that,   x  º  a i  (mod m i )    1  £  i  £  t     ......(1) The number x is unique in the following sense:   Let M be the product of all the m i ¢ s,   M = m 1 .m 2 ...m t   and y satisfies the system of congruences (1). Then,   y  º  x ( mod M)     Proof: We will use induction to prove this,            For x=a 1           here x is unique so, the result is true For t=1, Now, by the induction hypothesis, we assume it to be true for t=k     We will proof if the result is true for t=k+1   Consider the system of congruences, x  º  a 1  (mod m 1  )   x  º  a 2  (mod m 2  ) ...
Read more