As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
link to let me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
e-mail with your comments about this program (or anything else).
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
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
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,
Modified: February 18, 2016