Greatest Common Divisor (GCD)

GCD is the greatest number that evenly divides two or more given numbers. For example-GCD of 24 and 36 is 12 because 12 is the largest common divisor. Note that the GCD of a number is always a positive number.

GCD and LCM are two interrelated but different concepts. Let’s look at some key differences between them:

 

To find the GCD of two positive integers, we use the following steps:
 

1. We begin by listing all the divisors of a.
    
2. Then, list all the divisors of b.
    
3. Identify the common divisors of a and b.
    
4. The GCD is the largest common divisor out of the listed divisors.

      For example, let’s calculate the GCD of 40 and 60.

 

• Divisors of 40 = 1, 2, 4, 5, 8, 10, 20, 40.
   
• Divisors of 60 = 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.
   
• Common divisors = 1, 2, 4, 5, 10, 20.
   
• The greatest common divisor of these numbers is 20.
  
  So, we write: GCD (40, 60) = 20.

The greatest common divisor (GCD) obeys certain mathematical properties. Here are a few important ones:

 

Commutative Property


Since the order of the numbers does not change the final result, so GCD is commutative, i.e., GCD (a, b) = GCD (b, a)

For example: GCD(12, 18) = GCD (18, 12) = 6

 

Associative Property


The GCD is associative because the grouping of numbers does not change the result, i.e., GCD (a, GCD(b, c)) = GCD(GCD (a, b), c)

For example: 

First Grouping: GCD (8, GCD(12, 16))

GCD(12, 16) = 4

GCD(8, 4) = 4

So, GCD(8, GCD(12, 16)) = 4

 Second Grouping: GCD(GCD(8, 12), 16)

GCD(8, 12) = 4

GCD(4, 16) = 4

So, GCD(GCD(8, 12), 16) = 4

GCD (8, GCD(12, 16)) = GCD(GCD(8, 12), 16)

Hence, GCD is associative.


Distributive Property (Over LCM)


The GCD is distributive over the Least Common Multiple (LCM). 

GCD(a, LCM(b, c)) = LCM(GCD(a, b), GCD(a, c)).

For example:

GCD (8, LCM (12, 18)) = LCM (GCD (8, 12), GCD (8, 18))

Let’s look at the steps involved:

• LCM (12, 18) = 36
   
• GCD (8, 12) = 4
   
• GCD (8, 18) = 2
   
• LCM (4, 2) = 4
   
• GCD (8, 36) = 4
   

Therefore, 

GCD (8, LCM (12, 18)) = LCM (GCD (8, 12), GCD (8, 18)) holds true.

 

Divisibility Property


According to the divisibility property, if d is given as GCD (a, b), then it means d divides both a and b evenly. 
d ∣ a and d ∣ b where d = GCD ( a, b )

Example:
If d = GCD (18, 24) = 6, then 6 ∣ 18 and 6 ∣ 24. 

 

GCD with Zero


For any non-zero integer n, the GCD of 0 and n is n. However, the GCD of 0 and 0 is undefined because there is no greatest common divisor in this case.
 

GCD(0, n) = n, but GCD(0, 0) = undefined.
 

Example:
GCD(12, 0) = 12, but GCD(0, 0) is undefined.

 

Multiplicative Property


According to the multiplicative property of GCD, if a and b are co-prime, then:

GCD (a × b, c) = GCD (a, c) × GCD (b, c).

For example: 
Consider a = 7, b = 5, and c = 20.

Since 7 and 5 are co-prime;

(GCD(7,5) =1), GCD(7*5, 20) = GCD(7,20) * GCD(5,20) = 1*5 =5 

Hence, the property holds true.
 

Several significant theories lay the foundation of the Greatest Common Divisor. We will look at a few:


Euclidean Algorithm:


The Euclidean Algorithm is a method used to find the GCD of two numbers using repeated division. In this process, the division is repeated until we get 0 as the remainder. For any two positive integers a and b, the algorithm uses the relation a = bq + r.  

Here, any common divisor of a and b is also a common divisor of b and r. Therefore, the GCD of a and b can be written as:

GCD (a, b) = GCD (b, r)

 

Let’s take a look at this with an example: GCD (12, 10)


Step 1: Divide 12 by 10. Here, we get the remainder as 2.

So GCD (12, 10) = GCD (10, 2)


Step 2: Divide 10 by 2. Now, the remainder is 0. 

Since the remainder is 0. GCD (12, 10) = 2.
 

Prime Factorization Theory


Prime Factorization theory states that the GCD of two numbers is obtained by multiplying the common prime factors with the smallest exponent.

Example: GCD (90, 150)

Determine the prime factorization of the given numbers:

Prime factorization of 90: 2 × 32 × 5

Prime factorization of 150: 2 × 3 × 52

Common prime factors are 2, 3, and 5

Taking the smallest exponent for each number, we get, 21, 31, 51

Therefore, GCD is 21 × 31 × 51 = 30.

The Greatest Common Divisor helps students perform complex arithmetic problems easily. Here are a few tips and tricks that help students easily grasp the concept:

 

• Always remember that when a number is a multiple of another, the GCD is the smaller of the two. For example, GCD (64, 32) = 32.
  
   
• The GCD of two consecutive numbers will always be 1.
  
   
• There is just one common factor for co-prime numbers, i.e., 1.
  
   
• Apply the Euclidean Algorithm formula correctly.
  
   
• Formula: GCD(a, b) = GCD(b, a mod b), until the remainder is 0.