[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

[NumTh Expository] “Co-prime” as more basic than “Prime”

Introduction

     While mucking around with another problem, I used the above to argue and solve it.  If  a  is a factor (divisor) of  bk,  and  a  and  b  are co-prime (they do not have any common factor), then “obviously”  a  must divide  k.  I wanted to prove this by just using this definition of  a  and  b  being co-prime

          d | a  and  d | b   Þ   d | 1   Þ   d = 1  (since 1 | d  also)

The concept of being co-prime (or relatively prime) is more basic than the concept of prime numbers.  The prime number property

          p | ab  Þ   p | a  or  p | b

should be built on top of this common sense observation, instead of the other way round.  In advanced modern mathematics, the above prime number property is the definition of prime numbers.   By the way,  hcf  stands for highest common factor, which Americans call “greatest common divisor” or gcd.

     It turns out that “common sense” facts are harder to prove.  Furthermore, I wanted to tie one hand behind my back and still see if I could still do it.  I came up with three proofs.  In what follows, the notation  A | B | C  means  A | B  and  B | C  and by transitivity  A | C  and can be read as  “A  divides  B,  which divides  C”.

One more try ...

     I think the above proofs are correct as they stand, but I still have not achieved my objective of using just the concept of divisibility.  Proof #3 is short and sweet, but this borrows from the theory of Linear Diophantine Equations.  Looking back at proof  2a,  I decided to replace “prime number” with “smallest non-trivial divisor” and had a go at it again.  The observant reader will realise that the smallest non-trivial divisor is a prime number in disguise but “Shhhhhhh!  Don’t tell other people, OK?” 

Final Remark

     The key idea that makes this proof work is that the hcf is guaranteed to exist, and  hcf(A, B) always divides  AB  since it divides both  A  and  B.  Finally, I got the proof with the flavour that I wanted.  So how does the prime number property   p | ab  Þ   p | a  or  p | b    follow from the above theorem?  Easy: If  p  is a prime that does not divide  a,  then  hcf(p, a) = 1  i.e.  p  and  a  are coprime.  Then  p | b.  ©