[Introduction to Number Theory Series Part 10] How Is the Fundamental Theorem of Arithmetic Used in Actual Computation?

Prime factorization is not just a classification tool. It also turns several computations into clean structural rules.

What this post covers

• Why divisor counts come from exponent choices
• Why the gcd takes smaller exponents
• Why the lcm takes larger exponents
• Why prime factorization is a common computational base

Key terms

• fundamental theorem of arithmetic: unique prime factorization for integers greater than 1
• prime factorization: writing an integer as a product of primes
• greatest common divisor: the largest positive common divisor
• least common multiple: the smallest positive common multiple
• divisor: a number that divides another integer exactly

Why does the divisor count come from exponents?

Suppose

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

To form a divisor of 72, we can choose:

• for the factor 2: one of 2^0,2^1,2^2,2^3
• for the factor 3: one of 3^0,3^1,3^2

These choices are independent: choosing the exponent of 2 does not affect the choices for the exponent of 3, and vice versa. So the number of divisors is

$$(3+1)(2+1)=12.$$

Why does the gcd take smaller exponents?

Write

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

and

$$90=2\times 3^2\times 5.$$

The gcd must divide both numbers, so each prime can only appear as many times as it appears in both. If we chose a larger exponent for some prime, the result would fail to divide one of the two numbers. That forces us to take the smaller exponent:

$$\gcd(60,90)=2^1\times 3^1\times 5^1=30.$$

Why does the lcm take larger exponents?

The lcm must be a multiple of both numbers, so it has to include enough of each prime to cover both factorizations. If we chose a smaller exponent for some prime, the result would fail to be a multiple of one of the numbers. That forces the larger exponent:

$$\operatorname{lcm}(60,90)=2^2\times 3^2\times 5=180.$$

Another example

$$84=2^2\times 3\times 7, \qquad 126=2\times 3^2\times 7.$$

Then

$$\gcd(84,126)=2\times 3\times 7=42$$

and

$$\operatorname{lcm}(84,126)=2^2\times 3^2\times 7=252.$$

Why this matters

A single prime factorization can give us:

• divisor counts
• gcds with other numbers
• lcms with other numbers

and, in later topics, it also helps with other arithmetic functions.

So prime factorization is not just a trick. It is a structural tool.

Common mistakes

1. Memorizing formulas without the reason

The rules come from counting exponent choices and from the meaning of “divides both” versus “is a multiple of both.”

2. Swapping the gcd and lcm rules

gcd uses smaller exponents; lcm uses larger ones.

3. Ignoring factorization and guessing by intuition alone

That may work for small numbers but becomes unstable quickly.

Wrap-up

The fundamental theorem of arithmetic becomes powerful in practice once we read integers through prime exponents. That gives clean rules for divisor counts, gcds, and lcms.

Next we move into the third major block of the series: congruence, the language of remainders.