Find the greatest 4 digit number that will divide 63, 45 and 69 so as to leave the same remainder.
Tuesday, January 26, 2016
[S1_20160126FMNT] Largest Common Remainder for Three Divisors
Problem / Question
LCM + (smallest number – 1) = 7245 + 44 = 7289 J
This question is from National University of Singapore High School, which caters to students who are very interested in science and mathematics, and possibly an academic career. Do not be fooled by my short and sweet solution. The question is actually quite challenging, and I went by a long way before coming up with this elegant solution. This reminds me of Human Resource managers who think that more lines of code written by programmers means more work is done. Actually, a lot of hard thinking could be involved in writing a one-line code that does the same job.
Research shows that when expert problem solvers realise that they are stuck, they change tactics. They go back to the drawing board. “Insanity is doing the same thing over and over again and expecting the different results.” said Albert Einstein. The five stages of mathematical problem solving are
1. Understanding the problem
2. Planning a strategy
3. Executing the plan
5. Reflection (which can even include blogging about it!)
At the evaluation stage, if one finds that one is not getting the results, or if the approach is not elegant, one goes back to stage 2 to devise a new strategy. I had tried using a complicated Chinese Remainder Theorem approach, got the solution after one page of work, and realised that the problem can be solved very simply.
How does the solution work
The set of remainders dividing by 63, 45 and 69 repeat themselves in a cycle and the length of the cycle happens to be the Lowest Common Multiple (LCM). We can see this quite easily: suppose x and y both give a remainder R dividing by 63, 45 and 69, then x – y gives a remainder of 0 when divided by 63, 45 and 69, which means x – y is a common multiple of 63, 45 and 69, of which the lowest is the LCM.
It is a routine matter to get the LCM via prime factorisation as follows: 63 = 32 × 7, 45 = 32 × 5, and 69 = 3 × 23. We pick the highest power for each occurring prime and we obtain LCM = 32 × 5 × 7 × 23 = 7245.The next thing to note is that remainders must be less than the divisors. Hence the largest common remainder must be 44, one less than the smallest divisor. You cannot have a remainder of 45 when divided by 45, because you could simply have bumped up the quotient (the result of division) by 1 and get zero remainder. So from 7245, 7246, 7247, ... to 7289, you get common remainders of 0, 1, 2, ..., 44. Once you hit 7290, the remainder for division by 45 will hit 0 while the remainders for 63 and 69 will be 45 but this will not be a common remainder. The next time we get a common remainder will be 2×LCM = 2×7245 = 14490 which is 5 digits long. So within 4 digits, the highest number with a common remainder is 7289, which gives a common remainder of 44.
H04. Look for pattern(s)
H05. Work backwards
H09. Restate the problem in another way
H10. Simplify the problem
H13* Use Equation / write a Mathematical Sentence
* Lower Secondary Mathematics (Sec 1 ~ grade 7) challenge
* other syllabuses that involve factors and multiples or number theory
* any precocious or independent learner who loves a challenge