INTRODUCTION
I chose to explore the Chinese Remainder Theorem task as it was a topic I had no previous knowledge of, and wanted something to challenge & grow my current mathematical abilities & problem solving skills – which will allow me to better relate to students in the classroom and exam situations when they face difficult new topics & questions– and as a result, better adapt my teaching and level of guidance I need give my pupils – to maximize their learning potential and progress.
We will explore a question based on a quote by Fibonacci in his book Liber Abbaci (written in 1202),
where he says about the Chinese Remainder Theorem:
“Let a contrived number (the starting number) be divided by 3, also by 5, also by 7; and ask each time what remains from the division (modulo). For each unity that remains from the division by 3, retain 70; for each unity that remains from the division by 5, retain 21; and for each unity that remains from the division by 7, retain 15. And as much as the number surpasses 105, subrtract 105; and what remains to you is the contrived number.”
The Question: We will choose to explore if Fibonacci’s algorithm is always true,
and if not, to find out the general pattern and types of number it is true for.
Mason’s Framework of “Stuck, Aha, Check , and Reflect” from Thinking Mathematically will come in handy – to help us make progress when stuck – by getting us to associate to past thinking experience and strategies that worked for us successfully in the past (Page 16, Thinking Mathematically) –
By writing down “Stuck”, it gets us thinking about the problem – “I’ve been given so much information, I don’t know where to start”, “I don’t know if Fibonacci’s statement is always true”, “I don’t know how to find the general formula and the types of number it is true for” –
Which leads to more reflective questions:
- “What useful information have I been given? How can I find it?”
- “How can I see if Fibonacci’s statement is true? How can I prove it?”
- “What is a general formula?”, “What do I need to know to find the general formula?”, and
- “Which topics I’ve previously learnt in maths could I use to help me?”
Answering these questions can lead to the Aha moments – answering question 1:
“I can underline the key words to find the useful information and write down what the more difficult keywords mean to better understand what the question is telling me” (done that from the start)
Mason believes “To make progress we must be clear what the question is asking us”
but he adds, “this may not fully emerge until you’ve done a bit of doodling.”
(Page 1, Thinking Mathematically), which he believes
“Having underlined the key information from Fibonacci’s quote, I can see he outlines a step by step process to getting from the start number to the same end number”
“What is the step by step process?”
The step by step process is:
- Pick a starting number (let’s call it X)
- Divide X by 3, 5 and 7
- Find the remainder of each division:
X/3 has remainder a
X/5 has remainder b
X/7 has remainder c
Which we can re write more mathematically –
Find the Module of each division:
X mod 3 = a
X mod 5 = b
X mod 7 = c
Where a, b and c are whole numbers, such that 0 ≤ a <3, 0 ≤ b <5 and 0 ≤ c < 7
- Next multiply:
70 x a = 70a
21 x b = 21b
15 x c = 15c
- Then sum up the 3 calculations:
Sum = 70a + 21b + 15c and
- If Sum < 105, Sum should equal X
But If Sum > 105, calculate Sum – 105, where Sum – 105 should equal X
Answering question 2:
“I can see if Fibonacci’s statement is always true by trying out different examples”
which we will can do with Random Specialization –trying out random examples and substituting them into the algorithm.
Mason believes “By doing examples you make the question meaningful to yourself and you may also begin to see an underlying pattern in all the special cases which will be the clue to resolving the question completely.” (Thinking Mathematically, Page 2)
Doing examples will also help us better understand the question and be clear on what it’s asking us, which will allow us to make progress on the question (Mason, Thinking Mathematically, Page 1)
Even if the examples we try work, the process of finding the general formula and spotting patterns will tell us if Fibonacci’s process works for every number, and if not, what numbers they work for.
Answering question 3:
“The general formula is an equation where we input the starting number, and should get the same number as the output” – so we need to try out different numbers and experiment (just like before).
“We need to spot a pattern (a trend, relationship between the numbers) to
find the general formula”, but “how can we spot a pattern?”
By doing systematic specialization – trying out examples systematically (on a large scale, and consecutively, one after the other) – such as substituting every number in order from 1 to 100 as input into Fibonacci’s process and generating a list of numbers as the output – then analysing the list of numbers, looking at what type of number they are (even, odd, prime, a multiple of 3, 5, or 7, etc….) – will let us spot patterns and trends – and generalize a general formula.
Mason believes, spotting the underlying pattern in all the special cases will be the clue to resolving the question completely (Thinking Mathematically, Page 2).
We will use excel to test out numbers systematically, starting from 1 to 100,
then expanding the range to 200, 500, 1000, and even 10000 – to see the underlying pattern.
I will create 2 macros:
- To highlight the numbers that have the same input and output (and therefore work with Fibonacci’s statement)
- To put the highlighted numbers into a list (so we can analyse the numbers)
We will also test out different consecutive devisers (not just 3, 5 and 7) – to generate more lists of numbers and analyse them. I have a feeling we will have 2 general formulas – a general formula for specific set of devisers (such as the given 3, 5 and 7), and a more general formula that can work for any 3 consecutive devisers.
We will also use what Mason calls artful specialization to test and check our generalizations
and general formulas to check in the end.
Answering question 4:
“Algebraic Expression, Equations, Sequences, Modulo, Prime Factorization, Division Tests, Common Factors, Highest Common Factor & Lowest Common Denominator
are topics we might need”
- Algebraic Expressions – for the general type of number – as we can represent:
- Even numbers as 2k
- Odd numbers as 2k + 1
- Multiples of 3 as 3k, multiples of 5 as 5k, multiples of 7 as 7k, etc….
Where k is a positive integer
- Equations – to write the general formula
Modulo to calculate remainders
Prime Factorisizaion, Division Tests, HCF and LCM to help spot relationships
between the numbers which fit the criteria
We will also check and reflect on what we’re doing to correct any mistakes and adapt and improve our approach as we make progress exploring the problem.
A key thing to note is that Mason’s framework is a cycle that we can use over and over again – Not a one off linear process – but a tool to help us brainstorm and come up with all the possible questions and ideas to help us: get started solving the problem, make progress when we are stuck & furthermore provide us with a structure to solving the problem.
Fortunately, we have also been provided with extra guidance for our exploration by the teacher – that gives us a structure to follow for from start to finish to help us solve the problem:
A worked example of Fibonacci’s statement,
Example: Let the Contrived Number be 6
6/3 Remainder 0 0 x 70 = 0
6/5 Remainder 1 1 x 21 = 21
6/7 Remainder 6 6 x 15 = 90
0 + 21 + 90 = 111
111 – 105 = 6 Which was the contrived number
And 6 steps to follow and use as guides to make progress with our exploration:
- Try out some examples to understand what Fibonacci was talking about. Will it always work? (Computers might help)
- Find any connections between the divisors (3,5 and 7), their respective multipliers (70,21 and 15) and the subtractor 105
- Using the given divisors can you find another set of multipliers that will work
- For the set of divisors 2,3 and 5, can you find the associated multipliers and subtractor
- Can you generalise your results to other sets of relatively prime (ie their highest common factor is 1) divisors? [I feel its trying to say consecutively prime]
- Find some reading related to the Chinese Theorem
These fit naturally into Mason’s Framework of “Stuck, Aha, Check , and Reflect”– of the key questions and answers that we discussed in the Stuck and Aha phases –
and we will use this as a basis for our report.
Step 1 – Trying Out Examples (Random Specialization)
VIEW FULL ASSIGNMENT
To view and download the full assignment, purchase the assignment below: