## Meaning of Greatest Common Divisor

A divisor is a whole number (integer) that will go into another whole number without a remainder. The greatest common divisor is best explained with an illustration. The following table shows two numbers: 60 and 108, with all their divisors greater than 1.

There are divisors in the table that are not common to both 60 and 108. However, 2 is a common divisor to both numbers 60 and 108, but it is not the greatest divisor common to 60 and 108. Divisor 3 is similarly described. By inspection of the table, the greatest divisor that is common to both 60 and 108 is 12. No divisor above 12 is common in both 60 and 108. So 12 is the greatest common divisor for 60 and 108.

The aim of this article is to explain how to obtain Greatest Common Divisor by Subtraction or by Division; with programming done in Java.

## GCD by Subtraction

By inspection from the above table, the gcd for 60 and 108 is 12. This means that if 12 is added repeatedly, the result will become 60, the smaller of both numbers. If the addition of 12 continues, the result will become 108, the bigger of both numbers. That is:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

That is:

60 + 12 + 12 + 12 + 12 = 108

Which means:

60 + 48 = 108

If the addition of gcd can lead to both numbers, then maybe some form of continuous subtraction downwards can lead to the gcd. This is a fact, as illustrated by the following steps, beginning with the difference of 108 and 60 :

108 – 60 = 48

60 – 48 = 12

48 – 12 = 36

36 – 12 = 24

24 – 12 = 12

12 – 12 = 0

Between 60 and 108, 108 is the bigger number. After that, the difference of the resulting difference (48 for the first step) and the subtrahend (60 for the first step) is obtained repeatedly until the answer is zero. In the steps, the smaller number is subtracted from, the bigger number. At the last step, the minuend and the subtrahend are the same. This same value is the greatest common divisor.

Let the numbers whose gcd is needed be a and b. If these numbers have no gcd greater than 1, it means that their greatest common divisor is 1. In programming, the time complexity to find the gcd by subtraction is O(a+b). If a is 1 and b is 5, then the steps without programming will be:

5 – 1 = 4

4 – 1 = 3

3 – 1 = 2

2 – 1 = 1

1 – 1 = 0

The gcd here is 1. There are five steps here and not six steps by (a + b). However, in programming, the maximum possible number of code operations is what is taken as the time complexity.

## Coding GCD by Subtraction

The class and method for the greatest common divisor by subtraction in Java are:

int gcds(int a, int b) {

if (a == b)

return a;

if (a > b)

return gcds(a-b, b);

return gcds(a, b-a);

}

}

It begins with a statement for the last mathematical step when both resulting numbers are equal. The next two statements subtract the smaller number from the bigger number recursively. A Java main class and Java main method, to go with the above class, is:

public static void main(String args[]){

GCDS obj = new GCDS();

int ret = obj.gcds(108, 60);

System.out.println(ret);

}

}

The output is 12.

## GCD by Division

The above table is repeated here for easy reference:

The two numbers whose gcd is needed are 60 and 108, with 108 being the larger number. The above explanation for subtraction began with:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

That is:

60 + 12 + 12 + 12 + 12 = 108

Which means:

60 + 48 = 108

Modulo division is a division where the answer is the whole number part of the quotient, and the remainder is also taken into consideration. Consider the remainder when dividing 108 by 60 and remainders of the resulting quotients and their corresponding divisors.

108 % 60 = 48 (i.e 1 r 48)

60 % 48 = 12 (i.e 1 r 48)

48 % 12 = 0 (i.e 4 r 0)

The modulus division ends when the remainder is 0. The gcd is the divisor for the last step. It was already known, from the other method above, that the greatest common divisor is 12.

108 mod 60 is not zero. If the gcd between 60 and 108 had to be found by subtraction, the first difference for the gcd between 60 and 108 would be 48, and it can be shown that the gcd between 60 and 108 is 12. 60 mod 48 is not zero. If the gcd between 60 and 48 (the previous remainder) had to be found by subtraction, the first difference for the gcd between 60 and 48 would be 12, and it can be shown that the gcd between 60 and 48 is 12. 48 mod 12 is zero and has 0 remainders. If the gcd between 48 and 12 had to be found by subtraction, the first difference for the gcd between 48 and 12 would be 36. 36 is not the gcd between 48 and 12; however, 36 is a multiple of 12, which is the gcd.

Using any means, the reader can prove with the above steps that given that the gcd for 60 and 108 is 12, the gcd for 60 and 48 is also 12; and the gcd for 48 and 12 is still 12.

Consider another example to find the gcd by division. The problem now is: to find the gcd by division for the numbers 18 and 30.

Solution:

30 % 18 = 12 (i.e. 1 r 12)

18 % 12 = 6 (i.e. 1 r 6)

12 % 6 = 0 (i.e. 2 r 0)

The gcd is 6, read from the last line, where the modulus is 0.

30 mod 18 is not zero. If the gcd between 30 and 18 had to be found by subtraction, the first difference for the gcd between 30 and 18 would be 12, and it can be shown that the gcd between 30 and 18 is 6. 18 mod 12 is not zero. If the gcd between 18 and 12 had to be found by subtraction, the first difference for the gcd between 18 and 12 would be 6, and it can be shown that the gcd between 18 and 12 is 6. 12 mod 6 is zero. If the gcd between 12 and 6 had to be found by subtraction, the first difference for the gcd between 12 and 6 would be 6, and it can be shown that the gcd between 12 and 6 is 6. 6 is also a multiple of 6 itself, which is the gcd.

Using any means, the reader can prove with the above steps that given that the gcd for 30 and 18 is 6, the gcd for 18 and 12 is also 6; and the gcd for 12 and 6 is still 6.

Now consider the gcd obtained from 1 and 5 by division:

5 % 1 = 0 (i.e. 5 r 0)

There is only one step (one line) here. To end this section, note that the divisor at the last line, when looking for the gcd by division, is the gcd.

Also, note that:

gcd(a, b) = gcd(b, r)

where “a” and “b” are two different whole numbers and “r” is the remainder of the division between a and “b.” “b” may be bigger than “a,” or “a” may be bigger than b. This means that if the remainder of a division is not zero, then the greatest common divisor between the two numbers is the same as the greatest common divisor between the divisor and the remainder. The proof for this statement has been illustrated above.

This can go right down by modulo division, as experienced above until the remainder is zero. When the remainder is zero, this repeating rule does not hold. Strictly speaking, in modulus division, it does not matter whether “a” is bigger than b or b is bigger than “a”; the remainder is the same positive integer.

## Coding GCD by Division

If the greatest common divisor by the division between 60 and 108 is required mathematically, then the steps would be

108 % 60 = 48 (i.e 1 r 48)

60 % 48 = 12 (i.e 1 r 48)

48 % 12 = 0 (i.e 4 r 0)

Notice that it is the bigger number that is dividing, the smaller number. The Java class and method to do this division is:

int gcdd(int a, int b) {

if (a % b == 0)

return b;

return gcdd(b, a % b);

}

}

The first statement in the method accounts for the last mathematical step. The second statement does the modulo division. Both statements call the method recursively. The time complexity for gcd by division is O(log(a + b)). A good main class and the main method for this code are:

public static void main(String args[]){

GCDD obj = new GCDD();

int ret = obj.gcdd(108, 60);

System.out.println(ret);

}

}

The output is 12.

## Conclusion

The Greatest Common Divisor can be obtained by first subtracting the smaller number from the bigger number and then continuing to subtract the minuend from the difference or difference from the minuend, depending on which number is bigger.

The Greatest Common Divisor can also be obtained by first dividing the bigger number by the smaller number using modulus division; and then continuing to divide the remainder by the divisor or the divisor by the remainder, depending on which one is bigger, still by modulus division. Strictly speaking, in modulus division, it does not matter whether “a” is bigger than b or b is bigger than “a”; the remainder is the same positive integer.

This is done programmatically recursively.