``````
unit U_RemainderOf1;
{Copyright 2002, Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org

This program may be used or modified for any non-commercial purpose
so long as this original notice remains in place.
All other rights are reserved
}

{ What is the smallest multiple of 13 which leaves a remainder of 1 when
divided by each of the numbers 2 through 12?

We'll try 2 methods to find a solution:
1. Brute force- testing successive multiples of 13  until we find one
that leaves a remainder of 1 when divided by 2 througgh 12.
2, Find lowest common multiple (LCM) of 2 through 12 and
test successive (multiples of LCM) + 1 until we find one
divisible by 13
}

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ComCtrls;

type
TForm1 = class(TForm)
Memo1: TMemo;
SearchBtn1: TButton;
SearchBtn2: TButton;
Memo2: TMemo;
Memo3: TMemo;
StatusBar1: TStatusBar;
StatusBar2: TStatusBar;
procedure SearchBtn1Click(Sender: TObject);
procedure SearchBtn2Click(Sender: TObject);
end;

var  Form1: TForm1;

implementation
{\$R *.DFM}

var searchlimit:integer=100000;

{************** TForm1.SearchBtn1Clcik *********}
procedure TForm1.SearchBtn1Click(Sender: TObject);
var  i:int64;
j:integer;
solved:boolean;
start,stop,freq:int64;
begin
i:=13;
queryperformancecounter(start);
repeat
inc(i,26); {it has to remain odd}
solved:=true;
for j:=2 to 12 do
if i mod j <>1 then
begin
solved:=false;
break;
end;
until solved or (i>Searchlimit);
queryperformancecounter(stop);
queryperformancefrequency(freq);
if solved then showmessage(format('Solution is %8.0n,'
+#13+'Calculation time:  %8d microseconds',
[i+0.0, 1000000*(stop-start) div freq]))
else showmessage(format('No solutions less than %8.0n',[searchlimit+0.0]));
end;

{**************** GCD2 *************}
Function gcd2(a,b:integer):integer;
{return greated common denominator of a and b}
{Euclids method -  any number that divides a and b must divide a-b}

var g,z:integer;
begin
g:=b;
If b<>0 then
while g<>0 do
begin
z:=a mod g;
a:=g;
g:=z;
end;
result:=a;
end;

(*
{*************** GCD **************}
{Not used here but included for completeness}
Function GCD(A:array of integer):integer;
{Greatest Common Denominator of an array of integers}
var i,g:integer;
begin
g:=a[0];
if length(a)>=2 then
begin
g:=gcd2(g,a[1]);
if length(a)>2 then
for i:= 2 to length(a)-1 do g:=gcd2(g,a[i]);
end;
result:=g;
end;
*)

{*************** LCM ************}
Function LCM(A:array of integer):integer;
{Find the Lowest Common Multiple of an array of integers}
var i,x:integer;
begin
x:=a[0];
for i:=1 to length(a)-1 do x:=(x*a[i]) div gcd2(x,a[i]);
result:=x;
End;

{************** Tform1.SearchBtn2Click *********}
procedure TForm1.SearchBtn2Click(Sender: TObject);
var i,n:integer;
start,stop,freq:int64;
begin
queryperformancecounter(start);
n:=lcm([2,3,4,5,6,7,8,9,10,11,12]);
i:=0;
repeat
inc(i);
until ((i*n +1) mod 13 =0) or (i>10);
queryperformancecounter(stop);
queryperformancefrequency(freq);
if (i*n+1) mod 13 =0

then showmessage(format('LCM of [2..12] is %8.0n,'
+#13
+'Solution is %8.0n (%2.0n X %8.0n + 1),'
+#13+'Calculation time:  %8d microseconds'
,[n+0.0,i*n+1.0,i+0.0,n+0.0,
1000000*(stop-start) div freq]))
else showmessage(format('No solutions less than %8.0n',[i*n+1+0.0]));
end;

end.

``````