What is GCD? The Essential Guide for Every Aspiring Coder!
GCD, or Greatest Common Divisor, is one of the fundamental concepts in mathematics that represents the positive integer that divides two or more numbers. In this article, we will discuss what GCD is, what are the different methods to find GCD (Euclidean Algorithm Method and Prime Factorization Method), and how to calculate 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.
For example, let’s know how GCD can be used to solve the puzzle.
Three Glass Puzzles: You have 5, 8, and 12-litre milk containers. Each container has no marking except for that which gives you its total volume. You have an 8-litre container full of milk. You must use the container to measure out 6 liters of milk exactly. How is this done? GCD will help you out with this.
So, let’s start the article with the formal definition of GCD.
Table of Content
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
What is the 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 steps 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:
- Apart from these three methods, there are two other methods to find the GCD of two numbers: the Division-Based Method and the Divisor Method. However, both these methods are quite similar to the Euclidean Method and the Prime Factorization method, respectively.
- 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
- 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)
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)
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?
Answer:
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:
- Pour 8L of milk from the 12L container into the 8L container. Now, the 12L container has only 4L of milk left.
- Pour 5L of milk from 8L container to 5L container. Now, the 8L container has only 3L of milk left.
- Transfer all 5L milk from the 5L container to the 12L container. Now, the 5L container has 0L, the 8L container has 3L, and the 12L container has 9L.
- 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.
- Pour 8L of milk from the 12L container into the 8L container. Now, the 5L container has 3L, the 8L container has 8L, and the 12L container has 0L.
- 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.
- Transfer all 5L milk from the 5L container to the 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[0]]}L to {capacities[step[1]]}L: {volumes}")
# Verify the resultassert target in volumes, "The solution is incorrect"
Output
But what if you just want to know the number of steps required to get the result rather than the process? So, here, GCD comes into action. Let’s have a look at how GCD calculates 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[0], gcd(capacities[1], capacities[2])) # 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[0] != 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[0] == target: return current_state[0] 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}")
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 is 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 unravelling 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.
Top Picks & New Arrivals
