You are currently browsing the tag archive for the ‘Chinese remainder theore’ tag.

chineseremaindertheorem

The Chinese Remainder Theorem is a method to solve the following puzzle, posed by Sun Zi around the 4th Century AD.

What number has a remainder of 2 when divided by 3, a remainder of 3 when divided by 5 and a remainder of 2 when divided by 7?

There are a couple of methods to solve this.  Firstly it helps to understand the concept of modulus – for example 21 mod 6 means the remainder when 21 is divided by 6.  In this case the remainder is 3, so we can write 21 ≡ 3 (mod 6).  The ≡ sign means “equivalent to” and is often used in modulus questions.

Method 1:

1) We try to solve the first part of the question, What number has a remainder of 2 when divided by 3,

to do this we list the values of x ≡ 2 (mod 3).  x = 2,5,8,11,14,17……

2) We then look at the values in this list and see which ones also satisfy the second part of the question, What number has a remainder of 3 when divided by 5

From the list x = 2,5,8,11,14,17…… we can see that x = 8 has a remainder of 3 when divided by 5 (i.e 8  ≡ 3 (mod 5) )

3) We now start from 8 and count up in multiples of 15 (3 x 5 because we have mod 3 and mod 5 )

8, 23, 38, 53 …..

4) We look for a number on this list which satisfies the last part of the question, What number has a remainder of 2 when divided by 7?

With x = 8, 23, 38, 53 ….. we can see that x = 23 has a remainder of 2 when divided by 7 (i.e 23 ≡ 2 (mod 7) )

Therefore 23 satisfies all parts of the question.  When you divide it by 3 you get a remainder of 2, when you divide it by 5 you get a remainder of 3, and when you divide it by 7 you get a remainder of 2.  So, 23 is our answer.

The second method is quite a bit more complicated – but is a better method when dealing with large numbers.

Method 2

1) We rewrite the problem in terms of modulus.

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

We assign a = 2, b = 3, c = 2.

2) We give the values m1 = 3 (because the first line is mod 3), m2 = 5 (because the second line is mod 5), m3 = 2 (because the third line is mod 7).

3) We calculate M = m1m2m3 = 3x5x7 = 105

4) We calculate M1 = M/m1 = 105/3 = 35
M2 = M/m2 = 105/5 = 21
M3 = M/m3 = 105/7 = 15

4) We then note that M1 ≡ 2 (mod 3), M2 ≡ 1 (mod 5), M3 ≡ 1 (mod 7)

5) We then look for the multiplicative inverse of M1. This is the number which when multiplied by M1 will give an answer of 1 (mod 3). This number is 2 because 2×2 = 4 ≡ 1 (mod 3). We assign A = 2

We then look for the multiplicative inverse of M2. This is the number which when multiplied by M2 will give an answer of 1 (mod 5). This number is 1 because 1×1 = 1 ≡ 1 (mod 3). We assign B = 1.

We then look for the multiplicative inverse of M3. This is the number which when multiplied by M3 will give an answer of 1 (mod 7). This number is 1 because 1×1 = 1 ≡ 1 (mod 7). We assign C = 1.

6) We now put all this together:

x = aM1A + bM2B + cM3C (mod M)

x = 2x35x2 + 3x21x1 + 2x15x1 = 233 ≡ 23 (mod 105)

That last method may seem a lot slower – but when working with large numbers is actually a lot quicker.  So there we go – that’s the method that Sun Zi noted more than 1500 years ago.  This topic whilst seemingly quite abstract is a good introduction to number theory – the branch of mathematics which deals with the properties of whole numbers.

Essential resources for IB students:

1) Revision Village

Screen Shot 2021-05-19 at 9.55.51 AM

Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams.  I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.  

Screen Shot 2018-03-19 at 4.42.05 PM.png

There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions.  What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial.  Really useful!

Screen Shot 2021-05-19 at 10.05.18 AM

The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers.   These all have worked solutions and allow you to focus on specific topics or start general revision.  This also has some excellent challenging questions for those students aiming for 6s and 7s.

Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.

2) Exploration Guides and Paper 3 Resources

Screen Shot 2021-05-19 at 6.32.13 PM

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations.  The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.

Website Stats

  • 8,353,291 views

About

All content on this site has been written by Andrew Chambers (MSc. Mathematics, IB Mathematics Examiner).

New website for International teachers

I’ve just launched a brand new maths site for international schools – over 1500 pdf pages of resources to support IB teachers

Explore here!

Free HL Paper 3 Questions

Eight P3 investigation questions and fully typed mark scheme (around 240 marks)

Available to download here

IB Maths Exploration Guides

Three comprehensive pdf guides to help you get excellent marks on your maths exploration coursework.

Available to download here.

Recent Posts

Follow IB Maths Resources from Intermathematics on WordPress.com