Search
Support DFF
If you shop at Amazon anyway,
consider using this link. We receive a few cents from each purchase.
Thanks.
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.
Contact
Feedback:
Send an e-mail 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
=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;
|
