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
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
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
