Important properties of Greatest Common Divisor

 

Euclid's GCD Algorithm

One of the earliest known numerical algorithms is that developed by Euclid (the father of geometry) in about 300 B.C. for computing the greatest common divisor (GCD) of two positive integers.

Let GCD(x,y) be the GCD of positive integers x and y. If x = y, then obviously

GCD(x,y) = GCD(x,x) = x.

Euclid's insight was to observe that, if x > y, then

GCD(x,y) = GCD(x-y,y).

Actually, this is easy to prove. Suppose that d is a divisor of both x and y. Then there exist integers q₁ and q₂ such that x = q₁d and y = q₂d. But then

x - y = q₁d - q₂d = (q₁ - q₂)d. Therefore d is also a divisor of x-y.

Using similar reasoning, one can show the converse, i.e., that any divisor of x-y and y is also a divisor of x. Hence, the set of common divisors of x and y is the same as the set of common divisors of x-y and y. In particular, the largest values in these two sets are the same, which is to say that GCD(x,y) = GCD(x-y,y).

A Java method that implements Euclid's algorithm is as follows:

   int gcd(int K, int M) {
      int k = K;   // In order to state a simple, elegant loop invariant,
      int m = M;   // we keep the formal arguments constant and use 
                   // local variables to do the calculations.
      // loop invariant: GCD(K,M) = GCD(k,m)
      while (k != m) {
         if (k > m) 
            { k = k-m; }
         else 
            { m = m-k; }
      }
      // At this point, GCD(K,M) = GCD(k,m) = GCD(k,k) = k
      return k;
   }

As an example, suppose that we use this method to compute the GCD of 420 and 96. If we were to take a snapshot of the method's local variables immediately before the first loop iteration and immediately after each iteration, we'd get

When                         k     m
--------------------       ----- -----
Before 1st iteration        420   96
After 1st iteration         324   96
After 2nd iteration         228   96
After 3rd iteration         132   96
After 4th iteration          36   96
After 5th iteration          36   60 
After 6th iteration          36   24
After 7th iteration          12   24
After 8th iteration          12   12

A significant improvement in performance (in some cases) is possible, however, by using the remainder operator (%) rather than subtraction. Notice in the above that we subtracted m's value from k's four times before k became less than m. The same effect results from replacing k's value by k % m. (In this case, 420 % 96 is 36.) Using this approach forces us to change the loop condition, however, as here what will eventually happen is that one of k or m will become zero. (Indeed, k == m is impossible to arrive at unless K == M.) Note that GCD(x,0) = GCD(0,x) = x. (After all, x's greatest divisor is itself, which is also a divisor of zero.)

Our new method is as follows:

   int gcd(int K, int M) {
      int k = K;   // In order to state a simple, elegant loop invariant,
      int m = M;   // we keep the formal arguments constant and use 
                   // local variables to do the calculations.
      // loop invariant: GCD(K,M) = GCD(k,m)
      while (k !=0  &&  m != 0) {
         if (k > m)
            { k = k % m; }
         else
            { m = m % k; }
      }
      // At this point, GCD(K,M) = GCD(k,m) = max(k,m)
      return Math.max(k,m);
   }

Using this version of the method, we get the following snapshots:

When                         k     m
--------------------       ----- -----
Before 1st iteration        420   96
After 1th iteration          36   96
After 2nd iteration          36   24
After 3rd iteration          12   24
After 4th iteration          12    0

Notice that the number of loop iterations has been cut in half. Further code-simplification improvements are possible, however, by ensuring that k ≥ m. We can achieve this by replacing, on each iteration, k's value by m's and m's by k % m. This way, no if statement is needed:

   int gcd(int K, int M) {
      int k = Math.max(K,M);
      int m = Math.min(K,M);
      // loop invariant: k ≥ m ∧ GCD(K,M) = GCD(k,m)
      while (m != 0) {
         int r = k % m;
         k = m;
         m = r;
      }
      // At this point, GCD(K,M) = GCD(k,m) = GCD(k,0) = k
      return k;
   }

Using this version of the method, we get the following snapshots:

When                         k     m
--------------------       ----- -----
Before 1st iteration        420   96
After 1th iteration          96   36
After 2nd iteration          36   24
After 3rd iteration          24   12
After 4th iteration          12    0