|
|
Available Now
Search
Contact
Feedback:
Send an e-mail with your
comments about this program (or anything else).
Help support DFF
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.
|
| |
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
=a-qb so
r/M=a/M-qb/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.cut-the-knot.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;
|
