[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

[S1_AFMLCM_20150412] Conquering Algebraic Fractions

Question

Introduction

     This is an equation involving algebraic fractions, usually for secondary 1 (approximately grade 7) pupils in Singapore.  Many students (and teachers?) like to use the “cross-multiplying” method, as shown in Solution 1.  A usually more efficient method is to multiply every term by the Lowest Common Multiple (LCM) of all the denominators appearing in the equation, as shown in Solution 2.

Discussion

     Note that division by zero is not allowed.  Furthermore, in algebra, it is dangerous to cancel or divide by an unknown quantity, because there is a possibility that you are dividing by zero.  So any division or cancellation by an unknown quantity must be justified beforehand.  Mathematics is not a game of blind senseless manipulations.  If you look at the second solution, which is short and sweet (only 4 steps), multiplying through by the LCM of denominators not only avoids this awkwardness, but it clears all the fractions in one fell swoop.  The solution takes only  4  steps, and it is in fact the recommended method.  All students, whether “good” or “poor” in maths, should use the second method.  Teachers who refuse to use/teach the LCM method (out of habit, or because their own teachers taught them otherwise, or because this makes them or their pupils “uncomfortable”) are really doing the weaker students a huge disservice.  You are widening the achievement gap.  The better students are better, precisely because they use better methods.  The longer one’s working is, the higher the chances of making mistakes and the more time is wasted.  If the “weaker” pupils have to jump through lots of hoops to achieve a certain standard before they are allowed to learn this “advanced” method (actually it’s just the normal method), they will have to unlearn their old method and may get confused as they learn this method.  A triple whammy!  All learners need to practice anyway, so one might as well practice the correct thing right from the beginning and learn good habits (striving for efficient, effective, elegant solutions).  So please, please, please everyone: use the LCM method!

Suitable Levels

* Secondary 1 Mathematics

* GCE ‘O’ Level (“Elementary”) Mathematics Revision

* other syllabuses that involve algebraic Fractions

* precocious children who want to learn algebra