Search
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
feedback
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.
Thanks.
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.
Contact
Feedback:
Send an
email with your comments about this program (or anything else).

 
By definition, the Greatest Common Divisor (GCD) of two positive integers is the
largest integer which divides both integers exactly.
2000 years ago Mr. Euclid developed, or a least published, an algorithm
for finding the GCD of two numbers. His version was strictly geometrical
and depends on the fact that the the GCD of any two numbers a and b
(with a not less than b) is the same as the GCD of the b
and the remainder when a is divided by b.
Algebra hadn't been invented when Euclid published his
technique, but an algebraic proof looks like this:
Take any two positive integers a and
b with b smaller
than a. Euclid noted that there are
integers r and
q such that a=qb
+ r. (Just
divide b into a, then
q is the quotient and
r
is the remainder.)
Any common factor, N, of
b and r divides
a exactly : (N divides
b so it divides qb and it
divides r so it divides the sum,
qb +
r, which
is a of course.)
Any common factor, M, of
a and
b divides
r exactly
: (r
=aqb so
r/M=a/Mqb/M.
a/M
is an integer and qb/M is an integer so their difference,
r/M, is
an integer so M divides r.)
Note that all of the N's are
M's and all the
M's are N's
so the largest N must equal the largest M. In other
words: GCD(a,b) =
GCD(b,r). b is less than
a
and r is less than
b so we can repeat these steps substituting
b
for a and r for
b until r becomes
0.
the previous step has a=qb+0 and
b is the desired
GCD.

Here's an example of the algorithm in action
Find the GCD of 2322 and 654. Let a = 2322, b = 654
2322/654 =3. Remainder = 360 so gcd(2322, 654) = gcd(654, 360)
654/360 = 1, Remainder = 294 so gcd(654, 360) = gcd(360, 294)
360/294 = 1, Remainder = 66 so gcd(360, 294) = gcd(294, 66)
294/ 66 = 4, Remainder = 30 so gcd(294, 66) = gcd(66, 30)
66/30 = 2, Reaminder = 6 so gcd(66, 30) = gcd(30, 6)
30/6 = 5, Remainder 0 so gcd(30, 6) = 6
Therefore, gcd(2322,654) = 6.
Check http://www.cuttheknot.com/blue/Euclid.html
for more good info. Program PiCalc2 on this
site estimates of Pi by calculating the GCD of pairs of random integers.
A Sample Implementation in Delphi
Function
gcd(a,b:integer):integer;
{return greatest common denominator of a and b}
var g,z:integer;
begin
g:=b;
while g<>0 do
begin
z:=a mod g;
a:=g;
g:=z;
end;
result:=a;
end;
