Fundamental theorem of arithmetic — uniqueness of prime factorization

Question

What does the fundamental theorem of arithmetic state, why is uniqueness important, and how do we use prime factorization to find HCF and LCM?

Solution — Step by Step

Fundamental Theorem of Arithmetic: Every composite number can be expressed as a product of prime numbers, and this factorization is unique (apart from the order of the factors).

For example: $1200 = 2^4 \times 3 \times 5^2$

No matter how you factorize 1200, you will always get the same prime factors with the same powers. There is no other way to write it as a product of primes.

Without uniqueness, we could not define HCF and LCM using prime factors. The entire system of number theory rests on this theorem.

Consider: if 12 could be written as $2^2 \times 3$ AND also as some other product of primes, then finding common factors would be ambiguous. Uniqueness guarantees that the prime factorization is like a “fingerprint” — every number has exactly one.

Given two numbers, factorize both into primes:

HCF = product of common prime factors with the lowest power

LCM = product of all prime factors with the highest power

Example: Find HCF and LCM of 72 and 120.

$72 = 2^3 \times 3^2$

$120 = 2^3 \times 3 \times 5$

HCF = $2^3 \times 3^1 = 24$ (take lower powers)

LCM = $2^3 \times 3^2 \times 5 = 360$ (take higher powers)

For any two positive integers $a$ and $b$ :

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

Verification: $24 \times 360 = 8640$ and $72 \times 120 = 8640$ . It checks out.

This relationship is useful for finding LCM when HCF is known (or vice versa):

\text{LCM} = \frac{a \times b}{\text{HCF}}

This product relationship works for two numbers only. For three or more numbers, $\text{HCF} \times \text{LCM} \neq$ product of the numbers. CBSE boards have tested this distinction.

flowchart TD
    A["Prime Factorization of two numbers"] --> B["Write each as product of prime powers"]
    B --> C["HCF: take lowest power of each common prime"]
    B --> D["LCM: take highest power of each prime present"]
    C --> E["Multiply selected primes for HCF"]
    D --> F["Multiply selected primes for LCM"]
    E --> G["Verify: HCF times LCM = product of original numbers"]
    F --> G

Why This Works

HCF takes the minimum power because the highest common factor cannot contain a prime to a higher power than it appears in either number. LCM takes the maximum power because the least common multiple must be divisible by both numbers, so it needs at least as many of each prime as the “greedier” number requires.

The uniqueness of factorization ensures these definitions are well-defined — there is only one correct factorization to work from.

Alternative Method

For finding HCF, Euclid’s division algorithm is often faster than prime factorization (especially for large numbers). For LCM, once you have the HCF, use $\text{LCM} = \frac{a \times b}{\text{HCF}}$ rather than factorizing separately. This combination approach (Euclid for HCF, then formula for LCM) is the most efficient method overall.

Common Mistake

Students mix up which power to take: they use the highest power for HCF and the lowest for LCM. This is backwards. Remember: HCF is the Greatest Common Factor — but it takes the lowest power because it must be a factor of both numbers. LCM is the Least Common Multiple — but it takes the highest power because it must be a multiple of both. The names are about the result (greatest/least), the method uses opposite power choices.