What is GCD? The Essential Guide for Every Aspiring Coder!

# What is GCD? The Essential Guide for Every Aspiring Coder!

clickHere
Updated on Aug 31, 2023 10:32 IST

GCD or Greatest Common Divisor is one of the fundamental concepts in mathematics that represent the positive integer that divides two or more numbers. In this article, we will discuss what is GCD, what are the different methods to find GCD (Euclidean Algorithm Method, and Prime Factorization Method), and how to calculate the GCD using Python. Later in the article, we will discuss how GCD and LCM are related.

The GCD (or Greatest Common Divisor) is one of the fundamental concepts in mathematics and programming to calculate the greatest common divisor of two or more numbers, i.e., the Greatest Common Divisor refers to the largest number that can evenly divide two or more integers without leaving a remainder.

Let’s take an example, to know how GCD can be used to solve the puzzle.

Three Glass Puzzle: You have 5, 8, and 12-liter milk container, each container has no marking except for that which gives you its total volume. You have an 8-liter container full of milk. You must use the container in such a way as to exactly measure out 6 liters of milk. How is this done? GCD will help you out with this.

So, let’s start the article with the formal definition of GCD.

## What is Greatest Common Divisor?

The Greatest Common Divisor or GCD of two numbers is the largest number that divides both numbers without leaving a remainder.

For example, consider two numbers, 18 and 24.

• The Divisor of 18 is 1, 2, 3, 6, 9, and 18.
• The Divisor of 24 is 1, 2, 3, 4, 6, 8, 12, and 24.

The Largest Common Divisor in both 18 and 24 is 6.

Hence, the GCD of 18 and 24 is 6.
Note: It is also called the Highest Common Factor or HCF.

## Methods to Calculate the GCD

There are two important methods for calculating the GCD of two numbers:

### Euclidean Algorithm

Euclidean Algorithm is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number, i.e.,

GCD(252, 105) = GCD(252-105, 105) = GCD(147, 105) = 21

Steps to Find GCD Using Euclidean Algorithm

Let a and b be two numbers such that a > b.

• Divide the larger number a by the smaller number b
• Replace ‘a’ with ‘b’ and ‘b’ with the remainder from step-1
• Repeat step-1 and step-2 until the remainder is zero.
• Once you get the remainder of 0, the divisor will be the GCD of a and b at this stage.

Now, let’s take some examples to understand better how to use the Euclidean Algorithm to find the GCD of two numbers.

Example: Find the GCD of 48 and 18 using Euclidean Algorithm.

48 = 18 * 2 + 12

=> 18 = 12 * 1 + 6

=> 12 = 6 * 2 + 0

Hence, the GCD(48, 18) = 6.

Must Read: What is Euclidean Algorithm?

### Prime Factorization Method

It involves the breaking down of the numbers into their prime factors and then finding the product of the common term.

Let’s take an example to better understand how to find the GCD using prime factorization.

Example: Find the GCD of 18 and 48 using Prime Factorizations.

Prime Factorization of 18 is 2 x 3 x 3

Prime Factorization of 48 is 2 x 2 x 2 x 2 x 3.

The Common Factors are 2 and 3.

Now, multiplying the common prime factorization, we will get the GCD of 18 and 48, i.e., 2 x 3 = 6.

Hence, GCD (18, 48) = 6.

## Relation Between GCD and LCM

The greatest Common Divisor (GCD) and Least Common Multiple (LCM) are closely related, i.e., if you know one, you can find another.

Let’s consider if ‘a’ and ‘b’ are two numbers, then:

a * b = GCD (a, b) * LCM (a, b)

or GCD (a, b) = (a * b) / LCM (a, b)

The above formula shows that the Product of two numbers equals the Product of their GCD and LCM.

Let’s take an example (where a = 12 and b = 18) to understand better how to use the above formula,

The prime factorization of the two numbers 12 and 18 are:

12 = 2 * 2 * 3, and

18 = 2 * 3 * 3

then, GCD (12, 18) = 2 * 3 = 6, and

the LCM (12, 18) = 2 * 2 * 3 * 3 = 36

Now, multiplying GCD and LCM of 12 and 18 together, we get 216 (6 * 36).

Since 12 * 18 = 216 = GCD (12, 18) * LCM (12, 18)

=> a * b = GCD (a, b) * LCM (a, b)

Note:

1. Apart from these three above methods, there are two other methods to find GCD of two numbers, i.e., Division-Based Method and Divisor Methods. But both these methods are quite similar to the Euclidean Method and Prime Factorization method respectively.
2. GCD (a, b) = GCD (a, -b) = GCD (-a, b) = GCD (-a, -b) = GCD (b, a)
• Example: GCD (6, 9) = GCD (6, -9) = GCD (-6, 9) = GCD (-6, -9) = GCD (9, 6) = 3
3. GCD (a, b) = GCD (b, a) = GCD (a, b-a) = GCD (b, a-b)
• Example: GCD (10, 12) = GCD (12, 10) = GCD (10, 12-10) = GCD (12, 10-12) = 2

## Math’s Puzzle for GCD

### Twins Puzzle

Problem Statement: Two twin brothers, Ram and Shayam, have a collection of marbles. Ram has 36, while Shayam has 48. They want to divide their marbles into equal-sized groups without any marbles left over. What is the maximum number of equal-sized groups they create?

Answer: To solve this puzzle, we need to find the GCD of 36 and 48, i.e.,

36 = 2 * 2 * 3 * 3

48 = 2 * 2 * 2 * 2 * 3

Therefore, by the prime factorization method, GCD(36, 48) = 12

Hence, the twins can create a maximum of 12 equal-sized groups, i.e. each containing 12 marbles.

Now, let’s look at how to solve it in Python.

` `
```import math # Count of marbles for Ram and Shayamram_marbles = 36shayam_marbles = 48 # Find the GCD of the marble countsgcd = math.gcd(ram_marbles, shayam_marbles) # Calculate the maximum number of equal-sized groupsmax_groups = gcd print("The maximum number of equal-sized groups they can create is:", max_groups)Copy code```

Output

### Chocolate Bar Puzzle

Problem Statement: A, B, and C possess a variety of chocolate bars. A has 10, B has 15, and C has 20. They want to distribute their chocolate bars among themselves to ensure an equal number of chocolate bars for each person. What is the highest number of chocolate bars they can distribute equally?

To find the highest number of chocolate bars that can be equally distributed, we have to calculate the GCD of 10, 15, and 20.

Prime Factorization of:

10 = 2 * 5

15 = 3 * 5

20 = 2 * 2 * 5

Therefore, GCD (10, 15, 20) = 5, i.e., the maximum number of chocolate that can be distributed equally is 5.

Hence, each person will receive five chocolate bars.

Now, let’s look at how to solve it in Python.

` `
```import math # Number of chocolate bars for A, B, and Ca_bars = 10b_bars = 15c_bars = 20 # Find the GCD of the chocolate bar countsgcd = math.gcd(math.gcd(a_bars, b_bars), c_bars) # Calculate the maximum number of chocolate bars they can distribute equallymax_bars = gcd print("The maximum number of chocolate bars they can distribute equally is:", max_bars)Copy code```

Output

### Three Glass Puzzle

Problem Statement: You have 5, 8, and 12-liter milk container, each container has no marking except for that which gives you its total volume. You have an 8-liter container full of milk. You must use the container in such a way as to exactly measure out 6 liters of milk. How is this done? Find the minimum number of steps required to get the result?

Firstly, we will see how the steps to calculate the 6L milk and then using GCD we will calculate the minimum number of steps required to achieve the target.

Steps:

1. Pour 8L of milk from 12L in 8L conatiner. Now, the 12L container has only 4L of milk left.
2. Pour 5L of milk from 8L container to 5L container. Now, the 8L container has only 3L of milk left.
3. Transfer all 5L milk from 5L container to 12L conatiner. Now the 5L container has 0L, the 8L container has 3L, and the 12L container has 9L milk.
4. Transfer the remaining 3L milk from 8L milk to 5L milk container. Now the 5L container has 3L, the 8L container has 0L milk, and the 12L container has 9L milk.
5. Pour 8L of milk from 12L container to 8L container. Now the 5L container has 3L, the 8L container has 8L milk, and the 12L container has 0L milk.
6. Pour 2L of milk from 8L container to 5L container. Now, the 5L container has a 5L container, the 8L container has 6L milk, and the 12L container has only 1L of milk.
7. Transfer all 5L milk from 5L container to 12L container. Now, the 5L container has 0L milk, the 8L milk has 6L milk, and the 12L container has 6L milk.

Now, let’s have a python code for the above steps:

` `
```# Define the initial volumes of the containersvolumes = [0, 0, 12]  # Corresponding to 5L, 8L, and 12L containers # Define the capacities of the containerscapacities = [5, 8, 12]  # Corresponding to 5L, 8L, and 12L containers # The target volume we want to reachtarget = 6 # Function to pour from one container to anotherdef pour(source, target):    # The amount that can be poured is the minimum of the source volume and the remaining volume in the target    amount = min(volumes[source], capacities[target] - volumes[target])     # Update the volumes of the source and target    volumes[source] -= amount    volumes[target] += amount # Steps for pouring:# 12L -> 8L# 8L -> 5L# 5L -> 12L# 8L -> 5L# 12L -> 8L# 8L -> 5L# 5L -> 12L steps = [(2, 1), (1, 0), (0, 2), (1, 0), (2, 1), (1, 0), (0, 2)] #here 0: 5L container, 1: 8L container, 2: 12L container # Execute the stepsfor step in steps:    pour(*step)    print(f"After pouring from {capacities[step]}L to {capacities[step]}L: {volumes}") # Verify the resultassert target in volumes, "The solution is incorrect"Copy code```

Output

But, what if you just want to know the number of steps required to get the result, rather the process. So, here GCD will comes into action. let’s have a look how GCD will calculate the number of steps required to get the result.

` `
```from math import gcddef measure_milk(target):    # Define the capacities of the containers    capacities = [5, 8, 12]        # Set the initial state with 8 liters of milk in the 8-liter container    current_state = [8, 0, 0]        # Calculate the greatest common factor (GCF) of the capacities    gcf = gcd(capacities, gcd(capacities, capacities))        # Check if the target is divisible by the GCF    if target % gcf != 0:        return -1  # Target cannot be measured out            # Perform the pouring steps based on the GCF    while current_state != target:        for i in range(3):            for j in range(3):                if i != j:                    # Calculate the amount of milk that can be poured                    pour_amount = min(current_state[i], capacities[j] - current_state[j])                                        # Pour the milk and update the current state                    current_state[i] -= pour_amount                    current_state[j] += pour_amount                # Check if the target is reached        if current_state == target:            return current_state        return -1  # Target cannot be measured out # Call the function and print the minimum number of stepstarget_amount = 6minimum_steps = measure_milk(target_amount)print(f"The minimum number of steps required to measure out {target_amount} liters of milk is: {minimum_steps}")Copy code```

## Conclusion

In conclusion, the concept of GCD, or Greatest Common Divisor, holds significant importance in mathematics. It allows us to find the largest shared factor between numbers and simplifies fractions to their simplest form. GCD serves as a versatile tool, aiding in diverse areas such as number theory, cryptography, and modular arithmetic. By understanding the principles behind GCD and its relationship with the Greatest Common Divisor, we gain a deeper appreciation for the elegance and utility of this fundamental mathematical concept. Whether unraveling mathematical puzzles or solving real-world problems, GCD remains an invaluable asset in our mathematical toolkit.

Hope you will like the article.

Keep Learning!!

Keep Sharing!!

## FAQs

What is Greatest Common Divisor (GCD)?

The GCD (or Greatest Common Divisor) is one of the fundamental concepts in mathematics and programming to calculate the greatest common divisor of two or more numbers, i.e., the Greatest Common Divisor refers to the largest number that can evenly divide two or more integers without leaving a remainder.

What are the different methods to finds the GCD of two numbers?

Mainly, there are three different methods to find the GCD of two numbers Prime Factorization Methods, Divisor Method and Euclidean Method. But apart from these three you use long division method.

What is the relation between GCD and LCM?

If there are two numbers a and b, then product of two numbers is equal to the product of GCD and LCM of a and b.

Can GCD be negative?

No, GCD of two numbers cannot be negative. The sign of the input numbers does not affect the GCD.

Can GCD be used to simplify the fractions?

Yes, GCD is used to simplify fractions by dividing the numerator and denominator by their GCD to obtain the simplest form.

clickHere

Vikram has a Postgraduate degree in Applied Mathematics, with a keen interest in Data Science and Machine Learning. He has experience of 2+ years in content creation in Mathematics, Statistics, Data Science, and Mac... Read Full Bio

## Trending Technology Courses Data Structures
Coursera 4.1   Data Structures and Algorithms (III)
Coursera 4.0Starts today  ## Top Picks & New Arrivals        