Prime factorization means writing an integer as a product of prime numbers.
A prime number is a whole number greater than \(1\) with exactly two positive divisors:
\(1\) and itself.
\[
\begin{aligned}
1 \quad \text{and} \quad p.
\end{aligned}
\]
A composite number is a number greater than \(1\) that can be written as a product of smaller positive integers:
2. What prime factorization means
Prime factorization writes a positive integer \(n\ge2\) as a product of primes:
\[
\begin{aligned}
n &= p_1p_2p_3\cdots p_k.
\end{aligned}
\]
If the same prime appears multiple times, we combine the repeated factors into exponent form:
\[
\begin{aligned}
n &= p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}.
\end{aligned}
\]
Here each \(p_i\) is prime, and each exponent \(e_i\) is a positive integer.
3. Fundamental theorem of arithmetic
The Fundamental Theorem of Arithmetic says that every integer greater than \(1\)
has a unique prime factorization, except for the order of the factors.
For example:
\[
\begin{aligned}
840 &= 2^3\cdot3\cdot5\cdot7.
\end{aligned}
\]
The factors may be written in a different order, but the same primes and exponents must appear.
4. Repeated division method
A direct way to factor a number is repeated division by primes:
- Start with the smallest prime, \(2\).
- Divide by \(2\) as long as the division is exact.
- Then try \(3\), \(5\), \(7\), and so on.
- Whenever a prime divides the number exactly, record it as a factor.
- Stop when the remaining quotient is \(1\), or when the remaining quotient is prime.
5. Factor trees
A factor tree is a visual way to show prime factorization.
Start with the original number and split it into two factors.
Continue splitting every composite factor until all branch ends are prime.
For example:
\[
\begin{aligned}
840
&=84\cdot10\\
&=(12\cdot7)(2\cdot5)\\
&=(2\cdot2\cdot3)\cdot7\cdot2\cdot5\\
&=2^3\cdot3\cdot5\cdot7.
\end{aligned}
\]
The leaves of the factor tree are the repeated prime factors.
6. Worked example: factorize 840
Begin with \(840\). Divide by \(2\):
\[
\begin{aligned}
840\div2 &= 420,\\
420\div2 &= 210,\\
210\div2 &= 105.
\end{aligned}
\]
Now \(105\) is no longer divisible by \(2\). Try \(3\):
\[
\begin{aligned}
105\div3 &= 35.
\end{aligned}
\]
Now \(35\) is divisible by \(5\):
\[
\begin{aligned}
35\div5 &= 7.
\end{aligned}
\]
Finally, \(7\) is prime:
\[
\begin{aligned}
7\div7 &= 1.
\end{aligned}
\]
Therefore, the repeated prime factors are
\[
\begin{aligned}
2,\ 2,\ 2,\ 3,\ 5,\ 7.
\end{aligned}
\]
So:
\[
\begin{aligned}
840
&=2\cdot2\cdot2\cdot3\cdot5\cdot7\\
&=2^3\cdot3\cdot5\cdot7.
\end{aligned}
\]
7. Already-prime numbers
If the input number is already prime, its prime factorization is just itself.
For example:
\[
\begin{aligned}
97 &= 97.
\end{aligned}
\]
This means \(97\) cannot be broken into smaller prime factors.
8. Negative integers
Prime factorization is usually defined for positive integers greater than \(1\).
For a negative integer, we factor out \(-1\) first:
\[
\begin{aligned}
-840
&=-1\cdot840\\
&=-1\cdot2^3\cdot3\cdot5\cdot7.
\end{aligned}
\]
The prime part is the factorization of the positive number \(|n|\).
9. Why \(0\), \(1\), and \(-1\) are special
The number \(0\) does not have an ordinary prime factorization because every positive integer divides \(0\).
The numbers \(1\) and \(-1\) are called units; they are not prime.
\[
\begin{aligned}
1 &\text{ has no prime factors.}
\end{aligned}
\]
10. Exponents and repeated factors
Exponents count how many times a prime appears.
For example:
\[
\begin{aligned}
1024
&=2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\\
&=2^{10}.
\end{aligned}
\]
Exponent notation is shorter and easier to compare.
11. Divisor count from prime factorization
If
\[
\begin{aligned}
n &= p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m},
\end{aligned}
\]
then the number of positive divisors of \(n\) is
\[
\begin{aligned}
\tau(n)
&=(e_1+1)(e_2+1)\cdots(e_m+1).
\end{aligned}
\]
For \(840=2^3\cdot3^1\cdot5^1\cdot7^1\):
\[
\begin{aligned}
\tau(840)
&=(3+1)(1+1)(1+1)(1+1)\\
&=32.
\end{aligned}
\]
12. Radical of a number
The radical of \(n\), written \(\operatorname{rad}(n)\), is the product of the distinct prime factors of \(n\).
\[
\begin{aligned}
\operatorname{rad}(840)
&=2\cdot3\cdot5\cdot7\\
&=210.
\end{aligned}
\]
13. Perfect-square check
A positive integer is a perfect square exactly when every exponent in its prime factorization is even.
\[
\begin{aligned}
900
&=2^2\cdot3^2\cdot5^2.
\end{aligned}
\]
Since every exponent is even, \(900=30^2\).
14. Formula summary
| Concept |
Formula or rule |
Meaning |
| Prime factorization |
\(n=p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}\) |
Write \(n\) as a product of prime powers |
| Repeated factors |
\(840=2\cdot2\cdot2\cdot3\cdot5\cdot7\) |
Shows every prime factor individually |
| Exponent form |
\(840=2^3\cdot3\cdot5\cdot7\) |
Combines repeated primes |
| Divisor count |
\(\tau(n)=\prod(e_i+1)\) |
Counts positive divisors of \(n\) |
| Radical |
\(\operatorname{rad}(n)=p_1p_2\cdots p_m\) |
Product of distinct prime factors |
| Perfect square |
All exponents are even |
Determines whether \(n=k^2\) |
15. Common mistakes
- Stopping the factorization before all factors are prime.
- Forgetting repeated factors, such as writing \(840=2\cdot3\cdot5\cdot7\) instead of \(2^3\cdot3\cdot5\cdot7\).
- Counting \(1\) as a prime factor.
- Forgetting to factor out \(-1\) for negative inputs.
- Confusing a factor tree split with the final prime factorization.
Key idea: a factor tree is finished only when every branch ends in a prime number.
