Euclid and the GCD

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

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 e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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/Ma/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;

  

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.