[S1_20160126FMNT] Largest Common Remainder for Three Divisors

Problem / Question

Find the greatest 4 digit number that will divide 63, 45 and 69 so as to leave the same remainder.

Solution

     LCM + (smallest number – 1) = 7245 + 44 = 7289   J

Remarks

     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

     4. Evaluation

     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 = 3² × 7,   45 = 3² × 5,  and   69 = 3 × 23.  We pick the highest power for each occurring prime and we obtain  LCM = 3² × 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.

Heuristics Used

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

Suitable Levels

* 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