Problem Description
What is the smallest multiple of 13 which leaves a remainder of 1 when
divided by each of the numbers 2 through 12?
Background & Techniques
We'll try 2 methods to find a solution:
- Brute force- testing successive multiples of 13 until we find one
that leaves a remainder of 1 when divided by 2 through 12.
- Using LCM - find lowest common multiple (LCM) of 2 through 12.
This LCM, or any multiple of this LCM, plus 1 must leave a
remainder of 1 when divided by 2 through 12. We'll just start testing successive
multiples of LCM + 1 until we find one that is divisible by 13.
Process vs. Product
Like many of the problems here on DFF, the answer here is less
significant than the solving process. Because the code is so
simple, I've beefed it up just a little by adding the second solution
technique. It provides a good chance to review Lowest Common
Multiple (LCM) and it's relationship to Greatest Common Denominator
(GCD). Given two integers, a and b,
it is always the case that GCD(a,b)×LCM(a,b)=a×b.
There a GCD
page over in the Math Topics sect with more information about
GCD.
By the way, I learned Lowest Common Multiple, but current
usage seems to favor Least Common Multiple by about 3 to 1.
Google finds 2,100,000 "Least Common Multiple" references
and only 710,000 for "Lowest Common
Multiple"!!
One more "freebie" - it occurred to me that, aside from the
educational benefits of using the LCM method, it should be much
faster. About half a dozen extra lines of code, tells us the answer
- 70 times faster (636 vs. 9 microseconds on my Celeron 800mhz
system.) Windows procedures QueryPerformanceCounter and QueryPerofrmanceFrequency
make accurate timing pretty simple. Now if I can just make wise use
of the time saved!
Running/Exploring the Program
Suggestions for Further Explorations
???
| Original Date: August 24,
2002 |
Modified: November 07, 2008
|
|
