GCD (GCF) and LCM
The greatest integer that can divide two or more numbers simultaneously is called the Greatest Common Divisor (GCD) of these numbers, and the smallest positive integer that is simultaneously divisible by two or more numbers is called the Least Common Multiple (LCM) of these numbers.
Where a and b are two integers, the GCD of these two numbers is denoted as GCD(a, b), gcd(a, b), or \((a, b)_{gcd}\).
The LCM of these two numbers is denoted as LCM(a, b), lcm(a, b), or \((a, b)_{lcm}\). Furthermore, where a < b,
$$GCD (a, b) \le a < b \le LCM (a, b)$$ holds.
Example:
Let’s find the GCD and LCM of the numbers 18 and 24.
Positive divisors of 18: 1, 2, 3, 6, 9, 18
Positive divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24 (Note: 9 is corrected to 12 from the original text error)
Therefore, the set formed by the common positive divisors of these two numbers is {1, 2, 3, 6}. The largest element of this set, which is 6, is the greatest common divisor of the numbers 18 and 24. (GCD)
GCD (18, 24) = 6 is found.
Positive multiples of 18: 18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, 216, 234, …
Positive multiples of 24: 24, 48, 72, 96, 120, 144, 168, 192, 216, 240, …
Thus, the set of common positive multiples of 18 and 24 is {72, 144, 216, …}. The smallest element of this set, 72, is the least common multiple of 18 and 24. (LCM)
\(LCM(18, 24)=72\) is found.
Now, let’s find the gcd and lcm of 18 and 24 using prime factorization.
\[ \begin{array}{r r|l}
18 & 24 & 2 \\
9 & 12 & 2 \\
9 & 6 & 2 \\
9 & 3 & 3 \\
3& 1 & 3 \\
1 & & \\
\end{array} \]
Numbers that divide both 18 and 24 simultaneously:
\((18, 24)_{gcd}= 2\cdot 3=6\)
\((18, 24)_{lcm}= 2^3\cdot 3^2=72\) is found.
As a third method, let’s find the gcd and lcm of 18 and 24 by making use of their prime factorizations.
\(18=2\cdot 3^2 = 2\cdot 3 \cdot 3\)
\(24=2^3\cdot 3 =2 \cdot 2 \cdot 2 \cdot 3\)
The product of the common prime factors of 18 and 24 (2 and 3) gives the gcd of 18 and 24.
In other words, the gcd is found by multiplying the common prime factors with the smallest exponents.
\(18= 2\cdot 3 \cdot 3\)
\(24= 2 \cdot 2 \cdot 2 \cdot 3\)
From here, \((18, 24)_{lcm}=3\cdot 3 \cdot 2 \cdot 2 \cdot 2= 3^2 \cdot 2^3 =72 \). The lcm is found by multiplying the prime factors with the largest exponents.
Example:
Let’s find the gcd and lcm of the numbers 27 and 48.
First, let’s find the gcd and lcm by prime factorization.
\[ \begin{array}{r r|l}
27 & 48 & 2 \\
27 & 24 & 2 \\
27 & 12 & 2 \\
27 & 6 & 2 \\
27& 3 & 3 \to \text{Number that divides both 27 and 48 simultaneously}\\
9& 1 & 3 \\
3& & 3 \\
1 & & \\
\end{array}
\]
\[
gcd\,\,(27, 48)=3\\
\]
\[
lcm\,\,(27,48)=2^4 \cdot 3^3=432\\
\]
Now let’s find the gcd and lcm using the prime factorizations of 27 and 48. When finding the gcd, the product of the common prime factors of 27 and 48 with the smallest exponent is calculated (here it is only 3). When finding the lcm, the product of the prime factors of 27 and 48 with the largest exponent is calculated (note that 2 is multiplied even though it is not common).
Warning:
1. For numbers written in prime factorization form:
a) To find the GCD, take one from each of the common prime factors with equal exponents, and multiply them by the common prime factors with different exponents that have the smallest power.
b) To find the LCM, take one from each of the common prime factors with equal exponents, and multiply them by the common prime factors with different exponents that have the largest power, along with all of the non-common prime factors.
2. The gcd of coprime numbers is 1, and the lcm is equal to the product of these numbers.
3. The product of the gcd and lcm of two numbers is equal to the product of these two numbers. (This rule applies only to two numbers)
$$GCD (a,b) \cdot LCM (a,b)= a\cdot b$$
Example:
The weights of three separate sacks, each containing a different quality of sugar, are 48, 114, and 150 kilograms respectively. They will be filled into separate bags of equal weight, as large as possible, without any remaining sugar. Accordingly, let’s find how many bags are required for this job.
Since sugars of different qualities will be filled into bags of the maximum possible weight without being mixed together, let’s find the greatest common divisor of the numbers 48, 114, and 150.
\[
\begin{array}{r r r | l}
48 & 114 & 150 & 2\\
24 & 57 & 75 & 2 \\
12 & 57 & 75 & 2 \\
6 & 57 & 75 & 2 \\
3 & 57 & 75 & 3 \\
1 & 19 & 25 & 5 \\
& 19 & 5 & 5 \\
& 19 & 1 & 19 \\
& 1 & & \\
\end{array}
\]
Since \((48, 114, 150)_{gcd}=2 \cdot 3 =6\), the weight of each bag must be 6 Kilograms. From here:
\(48:6= 8\) Bags
\(114:6= 19\) Bags
\(150:6= 25\) Bags
Thus, 8 + 19 + 25 = 52 Bags are required for this task.
Example:
The surroundings of a rectangular field with dimensions \(68 \times 100 \text{ m}^2\) are to be planted with trees. Provided that the distance between the trees is equal and there must be a tree at each corner, let’s find the minimum number of saplings required for this task.
Since the number of saplings to be planted under the condition of equal distance will be minimized, the distance between the saplings must be as large as possible. Therefore, we need to find the gcd of 68 and 100.
Since \(68 = 2^2 \cdot 17\) and \(100= 2^2 \cdot 5^2 \), we find \( (68,100)_{gcd}=4 \). Thus, the maximum possible value of the distance between the saplings is 4 m.
The perimeter of the field is: \(2 \cdot (68 + 100) = 336 \) m. Accordingly, the minimum number of saplings required to plant along the perimeter of the field is found as \(336 \div 4 = 84\).
Example:
When Metin groups his pens into 4s, 5s, and 6s, there are always 3 pens left over each time. Let’s find the minimum number of pens Metin could have.
Subtracting 3 from the number of Metin’s pens gives a multiple of 4, 5, and 6. Accordingly, if we find the least common multiple of 4, 5, and 6:
\[
\begin{array}{r r r | l}
4 & 5 & 6 & 2\\
2 & 5 & 3 & 2 \\
1 & 5 & 3 & 3 \\
& 5 & 1 & 5 \\
& 1 & & \\\end{array}
\] (Note: Grid cleaned for standard calculation consistency)
\((4,5,6)_{lcm}= 60 \)
Therefore, the number of Metin’s pens minus 3 can be at least 60. Accordingly, Metin can have at least 63 pens.
Question 51:
Vinegar in barrels of 80 L, 100 L, and 120 L will be filled into cans of equal volume without being mixed together. Accordingly, what is the minimum number of cans required for this job?
\[ \text{A)} 9 \quad \text{B) } 11 \quad \text{C) } 15 \quad \text{D) } 17 \quad \text{E) } 20 \]
Solution:
Since the minimum number of cans of equal volume is required, the volume of the cans must be the greatest common divisor of 80, 100, and 120.
\((80,100,120)_{gcd}=20\) L. Since the volume of one can is 20 L:
$$ 80\div 20= 4$$ cans
$$100\div 20= 5$$ cans
$$120\div 20= 6$$ cans
Accordingly, a total of \(4+5+6= 15\) cans are required.
\({\textbf{Answer: C}}\)
Question 52:
What is the sum of the digits of the smallest natural number that leaves remainders of 1, 2, and 3 when divided by the numbers 3, 4, and 5, respectively?
\[ \text{A)} 5 \quad \text{B) } 7 \quad \text{C) } 8 \quad \text{D) } 10 \quad \text{E) } 13 \]
Solution:
The difference between the divisors 3, 4, 5 and their respective remainders 1, 2, 3 is 2 ($3-1=2$, $4-2=2$, $5-3=2$). This means that if we add 2 to our target number, it becomes exactly divisible by 3, 4, and 5. If we call the number x:
$$ x+2 =(3,4,5)_{lcm}=3 \cdot 4 \cdot 5 = 60 \Rightarrow x= 58 $$
Since 3, 4, and 5 are pairwise coprime numbers, their lcm is equal to their product. The sum of the digits of 58 is \(5 + 8 = 13\).
\({\textbf{Answer: E}}\)
Question 53:
How many rectangular prism-shaped blocks with dimensions \(4 \times 5 \times 6 \text{ cm}^3\) are needed to form a solid cube with the smallest possible volume?
\[ \text{A)} 2400 \quad \text{B) } 2250 \quad \text{C) } 2000 \quad \text{D) } 1800 \quad \text{E) } 1650 \]
Solution:
Since the volume of the cube is to be minimized, the length of its side must be the least common multiple of 4, 5, and 6. Therefore, \( (4, 5, 6)_{lcm}=60 \) cm.
Let x be the number of blocks required to obtain such a cube. Since the total volume of the rectangular blocks will be equal to the volume of the cube:
\( x \cdot (4\cdot 5 \cdot 6) = 60 \cdot 60 \cdot 60 \Rightarrow x \cdot 120 = 216000 \Rightarrow x = 1800 \) is found.
\({\textbf{Answer: D}}\)
Warning:
The GCD and LCM of fractional expressions \(\displaystyle\frac{a}{b}\) and \(\displaystyle\frac{c}{d}\):
\(GCD \left( \displaystyle \frac{a}{b} , \displaystyle\frac{c}{d} \right) =\displaystyle \frac{GCD(a, c)}{LCM(b, d)}\)
\(LCM \left( \displaystyle\frac{a}{b} ,\displaystyle \frac{c}{d} \right) = \displaystyle\frac{LCM(a, c)}{GCD(b, d)}\)
Example:
Let’s find the gcd and lcm of fractions \(\displaystyle\frac{6}{5}\) and \(\displaystyle\frac{12}{7}\).
\(GCD \left(\displaystyle \frac{6}{5} , \displaystyle\frac{12}{7} \right) = \frac{GCD(6, 12)}{LCM(5, 7)} =\displaystyle \frac{6}{35}\)
\(LCM \left( \displaystyle\frac{6}{5} , \displaystyle\frac{12}{7} \right) = \displaystyle\frac{LCM(6, 12)}{GCD(5, 7)} = \displaystyle\frac{12}{1} = 12\)
Question 54:
What is the smallest natural number that yields an integer result when divided by the numbers \(\quad \displaystyle \frac{9}{5}, \, \displaystyle\frac{12}{7}, \, \text{and } \displaystyle\frac{15}{11} \)?
\[ \text{A)} 90 \quad \text{B) } 180 \quad \text{C) } 240 \quad \text{D) } 270 \quad \text{E) } 360 \]
Solution 1:
Let the desired integer be x.
\[
{\large
\begin{array}{l l }
\displaystyle\frac{x}{\displaystyle\frac{9}{5}} = \displaystyle\frac{5 \cdot x}{9} \in \mathbb{Z} \\
\displaystyle\frac{x}{\displaystyle\frac{12}{7}} = \displaystyle\frac{7 \cdot x}{12} \in \mathbb{Z} \\
\displaystyle\frac{x}{\displaystyle\frac{15}{11}} = \displaystyle\frac{11 \cdot x}{15} \in \mathbb{Z} \\
\end{array}
}
\]
According to this, the number x must be a multiple of 9, 12, and 15.
Thus, the smallest value of x is:
\( x = (9,12,15)_{lcm} = 180\)
Solution 2:
\[\begin{array}{l l }
x = \text{LCM} \left( \displaystyle\frac{9}{5}, \displaystyle\frac{12}{7}, \displaystyle\frac{15}{11} \right) = \displaystyle\frac{\text{LCM}(9,12,15)}{\text{GCD}(5,7,11)}\\
x=\frac{180}{1} = 180
\end{array}\]
\({\textbf{Answer: B}}\)
Question 55:
What is the largest number that leaves a remainder of 11 when it divides both 151 and 171?
\[ \text{A)} 40 \quad \text{B) } 36 \quad \text{C) } 30 \quad \text{D) } 24 \quad \text{E) } 20 \]
Solution:
Let the desired number be x.
Since the remainders when 151 and 171 are divided by x are 11, subtracting 11 from these numbers—meaning the numbers 140 and 160—must be exactly divisible by x. Therefore, the largest number (x) that can divide both 140 and 160 completely is the greatest common divisor of these numbers.
Accordingly:
\[\begin{array}{l l }x=GCD(140,160)=20\end{array}\]
\({\textbf{Answer: E}}\)
Warning: (Practical Method)
When finding the GCD and LCM of two numbers, the following practical shortcut can be used: (For example, let’s find the GCD and LCM of 36 and 48)
1. Write a fraction using one of the given numbers as the numerator and the other as the denominator: \( \Large{ \frac{36}{48}} \)
2. Simplify this fraction to its lowest terms to form a proportion: \( \Large{ \frac{36}{48}= \frac{3}{4} } \)
3. In the resulting proportion, cross-multiplying the terms gives the lcm of these two numbers. Dividing the first term by the third term (or the second term by the fourth term) gives the gcd of these two numbers.
\[\begin{array}{l l }
LCM(36,48)=36 \cdot 4 = 144 \quad \text{(inner product)} \\
LCM(36,48)=48 \cdot 3 = 144 \quad \text{(outer product)} \\
\\
GCD(36,48)=36 \div 3 = 12 \quad \text{(first term divided by third term)} \\
GCD(36,48)=48 \div 4 = 12 \quad \text{(second term divided by fourth term)} \\
\end{array}\]
From here, we find:
\[\begin{array}{l l }LCM(36,48)=144\\GCD(36,48)=12\end{array}\]