Table of Contents
Prime factorization is about breaking a whole number down into a product of prime numbers. In the parent chapter “Divisibility and Primes” you have already met primes and divisibility, so here we focus on:
- What a prime factorization is
- How to find prime factorizations
- Why factorizations into primes are essentially unique
- Some uses of prime factorization
What is prime factorization?
A factorization of a positive integer $n$ is a way of writing $n$ as a product of integers greater than $1$.
A prime factorization of $n$ is a factorization of $n$ into prime numbers only. For example:
- $12 = 2 \cdot 2 \cdot 3$ is a prime factorization of $12$.
- $60 = 2 \cdot 2 \cdot 3 \cdot 5$ is a prime factorization of $60$.
It is common to group equal primes using exponents:
- $12 = 2^2 \cdot 3$
- $60 = 2^2 \cdot 3 \cdot 5$
Every prime number $p$ has the simplest possible prime factorization: just itself:
$$
p = p.
$$
By convention, $1$ is not written as a product of primes; it has no prime factorization, and we treat it as a special case.
Methods for finding prime factorizations
You already know how to test small primes and check divisibility from earlier material. Here we focus on standard systematic methods: factor trees and repeated division.
Factor trees
A factor tree is a diagram that shows how a number can be broken into factors step by step until only primes remain.
Example: Prime factorization of $72$.
- Start with $72$. Pick any nontrivial factorization, for instance $72 = 8 \cdot 9$.
- Factor $8$ and $9$ further:
- $8 = 2 \cdot 4$
- $9 = 3 \cdot 3$
- Factor $4$:
- $4 = 2 \cdot 2$
Now every “leaf” (end of each branch) is prime:
- $8 = 2 \cdot 2 \cdot 2$
- $9 = 3 \cdot 3$
So
$$
72 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 = 2^3 \cdot 3^2.
$$
Different choices at each step give different trees, but once you list and group the primes, you always get the same prime factorization.
Repeated division by primes
Another common method is repeated division by the smallest prime that divides the number.
Example: Prime factorization of $180$.
- Divide by $2$ as long as possible:
- $180 \div 2 = 90$
- $90 \div 2 = 45$
Now $ is no longer divisible by $. - Next prime is $3$:
- $45 \div 3 = 15$
- $15 \div 3 = 5$
- Now $5$ is prime.
So we have divided:
$$
180 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^2 \cdot 3^2 \cdot 5.
$$
You can arrange the steps in a table:
$$
\begin{array}{r|l}
2 & 180 \\
2 & 90 \\
3 & 45 \\
3 & 15 \\
5 & 5 \\
\hline
& 1
\end{array}
$$
The primes on the left are the prime factors.
When to stop factoring
In any method, you stop when all remaining factors are prime. Practically, that means:
- You have written your original number as a product:
$$
n = p_1 p_2 \cdots p_k
$$
where each $p_i$ is prime. - There is no need to “factor” further because primes have no nontrivial divisors other than $1$ and themselves.
If you are using repeated division and you have reduced the number down to $1$, then you have completely factored it.
The Fundamental Theorem of Arithmetic (idea)
The central theoretical fact behind prime factorization is:
Fundamental Theorem of Arithmetic (informal).
Every integer $n \ge 2$ can be written as a product of prime numbers, and this factorization is unique apart from the order of the factors.
“Unique apart from order” means:
- $12 = 2 \cdot 2 \cdot 3$ and $12 = 2 \cdot 3 \cdot 2$ are the same prime factorization,
- but you will never have a completely different list of primes (for example, $12$ cannot equal $2 \cdot 5$ or $3 \cdot 4$ as prime-only products).
This theorem justifies talking about the prime factorization of a number.
You will see more formal proofs and reasoning in other chapters on logic and proofs; here we use the idea as a tool.
Using prime factorization
Prime factorizations are powerful because they turn questions about divisibility and arithmetic into questions about exponents.
Assume
$$
a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \qquad
b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k},
$$
where $p_1, \dots, p_k$ are the distinct primes that appear in either $a$ or $b$, and exponents can be zero if a prime does not actually appear.
Testing divisibility via prime factors
A number $a$ divides $b$ (written $a \mid b$) exactly when, for every prime $p$, the exponent of $p$ in $a$ is less than or equal to the exponent of $p$ in $b$.
Example: Does $18$ divide $540$?
- $18 = 2^1 \cdot 3^2$
- $540 = 2^2 \cdot 3^3 \cdot 5$
Compare exponents:
- For prime $2$: $1 \le 2$
- For prime $3$: $2 \le 3$
So $18 \mid 540$.
Greatest common divisor (gcd) via prime factors
If you know the factorizations of $a$ and $b$, their greatest common divisor $\gcd(a,b)$ can be found by taking the minimum exponents of each prime:
$$
\gcd(a,b) = p_1^{\min(\alpha_1,\beta_1)} p_2^{\min(\alpha_2,\beta_2)} \cdots p_k^{\min(\alpha_k,\beta_k)}.
$$
Example: $\gcd(72, 180)$.
- $72 = 2^3 \cdot 3^2$
- $180 = 2^2 \cdot 3^2 \cdot 5$
For each prime:
- For $2$: $\min(3,2) = 2$
- For $3$: $\min(2,2) = 2$
- For $5$: $\min(0,1) = 0$ (so $5^0 = 1$, which we usually omit)
Thus:
$$
\gcd(72, 180) = 2^2 \cdot 3^2 = 36.
$$
Formal algorithms for the gcd (like the Euclidean algorithm) are treated elsewhere; here the focus is how prime factors encode the same information.
Least common multiple (lcm) via prime factors
The least common multiple $\operatorname{lcm}(a,b)$ can be obtained by taking the maximum exponents of each prime:
$$
\operatorname{lcm}(a,b) = p_1^{\max(\alpha_1,\beta_1)} p_2^{\max(\alpha_2,\beta_2)} \cdots p_k^{\max(\alpha_k,\beta_k)}.
$$
Continuing the example: $\operatorname{lcm}(72, 180)$.
- $72 = 2^3 \cdot 3^2$
- $180 = 2^2 \cdot 3^2 \cdot 5$
For each prime:
- For $2$: $\max(3,2) = 3$
- For $3$: $\max(2,2) = 2$
- For $5$: $\max(0,1) = 1$
So:
$$
\operatorname{lcm}(72, 180) = 2^3 \cdot 3^2 \cdot 5 = 360.
$$
There is an important relationship:
$$
\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b,
$$
which can also be understood using prime exponents.
Simplifying fractions using prime factorizations
When you have a fraction $\dfrac{a}{b}$ with $a$ and $b$ positive integers, factoring numerator and denominator into primes makes simplification straightforward.
Example: Simplify $\dfrac{180}{252}$.
Factor each:
- $180 = 2^2 \cdot 3^2 \cdot 5$
- $252 = 2^2 \cdot 3^2 \cdot 7$
Cancel common prime factors:
$$
\frac{2^2 \cdot 3^2 \cdot 5}{2^2 \cdot 3^2 \cdot 7}
= \frac{5}{7}.
$$
In effect, you are dividing numerator and denominator by their gcd, which can be seen directly from their prime factorizations.
Typical patterns and observations
Some useful special cases and patterns:
- If the prime factorization of $n$ is
$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k},
$$
then every positive divisor of $n$ has the form
$$
p_1^{\gamma_1} p_2^{\gamma_2} \cdots p_k^{\gamma_k}
$$
with \le \gamma_i \le \alpha_i$ for each $i$.
- If $n$ is a perfect square, then in its prime factorization all exponents are even (for example, $144 = 2^4 \cdot 3^2$).
- If $n$ is a perfect cube, then in its prime factorization all exponents are multiples of $3$.
These patterns are heavily used later in number theory and in various problem-solving techniques.
Limitations and practical notes
For small to moderately large integers, the methods described (factor trees, repeated division) are perfectly adequate. For very large integers, especially in cryptographic applications, finding prime factorizations becomes difficult and requires more advanced algorithms, which are beyond this chapter.
Here you should aim to:
- Be comfortable writing numbers up to at least a few thousand as products of primes.
- Move fluently between a number and its prime exponent form.
- Use prime factorization to reason about divisibility, gcd, lcm, and simplification of fractions.
These skills form a basic toolkit for many topics later in number theory and beyond.