Tenth Grade Mathematics: Prime Factorization: HCF and LCM
The Highest Common Factor (HCF) and Lowest Common Multiple (LCM) are fundamental mathematical constructs that govern common divisibility and synchronized periodic cycles. While Euclid's algorithm provides an efficient route for finding the HCF of two numbers, the prime factorization method delivers a profound visual and structural understanding of both HCF and LCM simultaneously. By decomposing integers into their constituent prime powers, we can determine common factors, shared multiples, and their foundational algebraic relationship.
Principles of HCF and LCM through Prime Powers
Let two or more composite numbers be written in their canonical prime factorization forms. The definitions of HCF and LCM can be directly stated in terms of prime powers:
1. Highest Common Factor (HCF):
The product of the smallest power of each common prime factor involved
in the numbers.
2. Lowest Common Multiple (LCM):
The product of the greatest power of each prime factor involved in the
numbers (common or uncommon).
Visual Representation using Prime Venn Diagram for Numbers A and B:
+-------------------------------------------------------------+
| Number A Factors Number B Factors |
| +-----------+ |
| Unique to A | Common | Unique to B |
| Factors | Factors | Factors |
| (Unshared) | (HCF) | (Unshared) |
| +-----------+ |
| <----------------------- LCM -----------------------------> |
+-------------------------------------------------------------+
Detailed Example: HCF and LCM of 72 and 120
Consider the canonical prime factorizations of 72 and 120:
72 = 2^3 * 3^2
120 = 2^3 * 3^1 * 5^1
Prime Factors involved: 2, 3, 5
For HCF (Common primes with lowest powers):
- Common prime 2: lowest power is 2^3 = 8
- Common prime 3: lowest power is 3^1 = 3
- Prime 5 is not common to both numbers (power in 72 is 5^0).
HCF(72, 120) = 2^3 * 3^1 = 8 * 3 = 24
For LCM (All primes with highest powers):
- Prime 2: highest power is 2^3 = 8
- Prime 3: highest power is 3^2 = 9
- Prime 5: highest power is 5^1 = 5
LCM(72, 120) = 2^3 * 3^2 * 5^1 = 8 * 9 * 5 = 360
The Fundamental Product Relationship
A vital theorem connects the HCF, LCM, and the product of any two positive integers:
Theorem: For any two positive integers a and b:
HCF(a, b) * LCM(a, b) = a * b
Algebraic Verification of the Relationship
Let p be any prime factor present in the prime factorizations of positive integers a and b. Suppose the power of p in a is p^x and the power of p in b is p^y, where x and y are non-negative integers.
In the calculation of HCF(a, b), the exponent assigned to p is min(x, y). In the calculation of LCM(a, b), the exponent assigned to p is max(x, y).
When we multiply HCF(a, b) by LCM(a, b), the power of the prime p in the product is:
Exponent in [HCF * LCM] = min(x, y) + max(x, y)
For any two real numbers x and y, the sum of the minimum and the maximum is always identically equal to the sum of the numbers themselves: min(x, y) + max(x, y) = x + y.
Therefore, the exponent of p in HCF(a, b) * LCM(a, b) is exactly x + y, which is identically the exponent of p in the product a * b. Because this holds true for every prime factor, the identity HCF(a, b) * LCM(a, b) = a * b is established.
Important Limitation: Three or More Integers
It is critical to note that this simple formula does not hold for three or more integers:
HCF(a, b, c) * LCM(a, b, c) != a * b * c (In general)
To find the LCM of three numbers using their HCFs, one must use the generalized inclusion-exclusion formulation:
LCM(a, b, c) = (a * b * c * HCF(a, b, c)) / (HCF(a, b) * HCF(b, c) * HCF(c, a))
Real-World Applications: Synchronization and Packaging
Problems involving periodic synchronization, such as traffic lights changing together or runners circling a track, require calculating the LCM to find the earliest point of simultaneous repetition. Conversely, problems involving partitioning resources into equal groups without waste require calculating the HCF.
+------------------------+------------------------------------+
| Problem Requirement | Mathematical Tool |
+------------------------+------------------------------------+
| Dividing into equal | Highest Common Factor (HCF) |
| bins, largest tile | |
+------------------------+------------------------------------+
| Repeating cycles, | Lowest Common Multiple (LCM) |
| simultaneous bells | |
+------------------------+------------------------------------+
Chapter Exercises
Exercise 1: Find the HCF and LCM of 336 and 54 using the prime factorization method, and verify that HCF(336, 54) * LCM(336, 54) = 336 * 54.
Exercise 2: Three bells toll together at intervals of 9, 12, and 15 minutes respectively. If they toll together now, after how many hours will they toll together again?
Exercise 3: Find the HCF and LCM of the three integers 12, 15, and 21 using the prime factorization method. Verify whether HCF(12, 15, 21) * LCM(12, 15, 21) equals 12 * 15 * 21.
Solutions and Explanations
Solution 1: First find the canonical prime factorizations of 336 and 54. Dividing 336 successively by primes gives 336 = 2^4 * 3^1 * 7^1. Dividing 54 gives 54 = 2^1 * 3^3. For HCF, take the lowest powers of the common primes 2 and 3: HCF(336, 54) = 2^1 * 3^1 = 6. For LCM, take the highest powers of all primes: LCM(336, 54) = 2^4 * 3^3 * 7^1 = 16 * 27 * 7 = 3024. Now verify the product relationship: HCF * LCM = 6 * 3024 = 18144. Computing the product of the numbers: 336 * 54 = 18144. Since both products equal 18144, the formula is verified.
Solution 2: The time interval after which the three bells toll together simultaneously is the lowest common multiple of their individual intervals. We find LCM(9, 12, 15). Factor each number into primes: 9 = 3^2, 12 = 2^2 * 3^1, and 15 = 3^1 * 5^1. The LCM is obtained by taking the highest power of each prime factor present: LCM = 2^2 * 3^2 * 5^1 = 4 * 9 * 5 = 180 minutes. Converting minutes to hours: 180 / 60 = 3 hours. Thus, the three bells will toll together again after exactly 3 hours.
Solution 3: Factor the three integers into primes: 12 = 2^2 * 3^1, 15 = 3^1 * 5^1, and 21 = 3^1 * 7^1. The only common prime factor present in all three numbers is 3, appearing with power 1, so HCF(12, 15, 21) = 3. For LCM, collect the highest power of each prime: LCM(12, 15, 21) = 2^2 * 3^1 * 5^1 * 7^1 = 4 * 3 * 5 * 7 = 420. Now compute HCF * LCM = 3 * 420 = 1260. On the other hand, the product of the three numbers is 12 * 15 * 21 = 3780. Because 1260 != 3780, this explicitly demonstrates that HCF(a, b, c) * LCM(a, b, c) does not equal a * b * c for three numbers.