Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two positive integers a and b is the largest positive number that divides both numbers exactly, without leaving any remainder. The GCD is always a positive value and never zero, because even if two numbers have no other common factors, they will always have 1 as a common divisor. The full form of GCD is Greatest Common Divisor. In simple terms, it is the largest number that divides a set of positive numbers without leaving a remainder.
 

Let see an example: Find the GCD of 18 and 24
 

Step 1: List the factors of each number

Factors of 18: 1, 2, 3, 6, 9, 18

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
 

Step 2: Identify the common factors

Common factors: 1, 2, 3, 6
 

Step 3: Choose the greatest (largest) common factor

The greatest common factor is 6
 

Final Answer: GCD(18, 24) = 6
 

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 LCM method is another way to find the GCD of two positive integers, a and b.
According to this method, the GCD can be found using this formula:
 

\(\text{GCD}(a,b) = \frac{a \times b}{\text{LCM}(a,b)}\)
 

This means that once you know the Least Common Multiple (LCM) of two numbers, you can easily calculate their GCD by dividing the product of the two numbers by their LCM.
 

To find the GCD of two numbers a and b using their LCM, follow these simple steps:

Multiply the numbers:

Calculate the product a × b.

Find the LCM:
Determine the Least Common Multiple of a and b.

Divide:
Divide the product a × b by the LCM.

Get the GCD:
The answer you get from the division is the Greatest Common Divisor (GCD) of the two numbers.
 

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.
   
• Show the Greatest Common Divisor in everyday situations, like sharing chocolates or arranging chairs in rows.
   
• Begin with small numbers to easily identify common factors. Gradually increase difficulty as children become confident with the Greatest Common Denominator.
   
• Teach children to list all factors of each number and identify the most significant common factor. This reinforces the Greatest Common Divisor formula clearly and visually.
   
• Explain that GCD is about dividing numbers into equal groups. Encourage exercises using multiplication and division to strengthen understanding.
   

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.