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:
 

Step 1: We begin by listing all the divisors of a.
 

Step 2: Then, list all the divisors of b.
 

Step 3: Identify the common divisors of a and b.
 

Step 4: The GCD is the largest common divisor out of the listed divisors.

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

Step 1: Divisors of 40 = 1, 2, 4, 5, 8, 10, 20, 40.
 

Step 2: Divisors of 60 = 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.
 

Step 3: Common divisors = 1, 2, 4, 5, 10, 20.
 

Step 4: 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, 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 × 3² × 5\)

Prime factorization of \(150: 2 × 3 × 5²\)

Common prime factors are 2, 3, and 5

Taking the smallest exponent for each number, we get, \(2¹, 3¹, 5¹ \)

Therefore, GCD is \(2¹ × 3¹ × 5¹ = 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 any two consecutive numbers is always 1.
  
   
• There is just one common factor for co-prime numbers, and that is 1.
  
   
• Apply the Euclidean Algorithm formula correctly.
  
   
• Formula: GCD \((a, b) =\) GCD (b, a mod b), until the remainder is 0.
   

Greatest Common Divisors (GCD) are useful in everyday lives in many ways, and some of them are listed below. 
 

• Simplifying fractions: To reduce a fraction like \(\frac{36}{48} \) to its lowest terms, we have to divide numerator and denominator by their GCD, which is 12. Thus, the result becomes \(\frac{3}{4} \). This is a direct daily use of GCD in schoolwork and budgeting. 
  
   
• Sharing items equally without remainder: While distributing identical items like candies, pencil or gifts, among the children with nothing being left over, GCD tells the maximum size of each equal share. 
  
   
• Working with time schedules and repeated events: When events repeat at different intervals, and you want a common time when they align, GCD helps. For instance, one signal flashes every 8 minutes and another every 12 minutes, the next time they flash together is every GCD \((8,12) = 4\) minutes. 
  
   
• Breaking down large numbers in engineering: In allocating resources like materials, wires and so on, in equal segments without leftover, engineers uses GCD. 
  
   
• Music and rhythms: In music, if two rhythms repeat after different counts, the point where they sync is the GCD. Musicians and composers often use this kind of reasoning for overlays, beats and loops.