Prime Factorization

Every whole number greater than $1$ is either prime or composite, and every composite number can be broken down into a unique product of prime factors. This idea — called the fundamental theorem of arithmetic — is one of the most important facts in all of mathematics. Prime factorization is the tool that makes GCF and LCM calculations systematic, simplifies fractions efficiently, and builds the foundation for algebra topics like factoring polynomials.

Prime vs Composite Numbers

Prime Numbers

A prime number is a whole number greater than $1$ that has exactly two factors: $1$ and itself.

The first several prime numbers are:

$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ \ldots$

Key facts about primes:

• $2$ is the only even prime. Every other even number is divisible by $2$ (and therefore has more than two factors).
• $1$ is neither prime nor composite. By convention, $1$ is excluded because it has only one factor (itself).
• There are infinitely many primes. No matter how far you count, there are always more primes ahead.

Composite Numbers

A composite number is a whole number greater than $1$ that has more than two factors. In other words, it can be divided evenly by at least one number other than $1$ and itself.

Examples: $4, 6, 8, 9, 10, 12, 14, 15, \ldots$

Example 1: Classify Numbers as Prime or Composite

Classify: $17$, $21$, $2$, $51$

• $17$: factors are $1$ and $17$ only. Prime.
• $21$: $21 = 3 \times 7$, so it has factors $1, 3, 7, 21$. Composite.
• $2$: factors are $1$ and $2$ only. Prime. (The smallest and only even prime.)
• $51$: digit sum $= 5 + 1 = 6$, divisible by $3$. $51 = 3 \times 17$. Composite.

How to Test if a Number Is Prime

To check whether a number $n$ is prime, test for divisibility by every prime up to $\sqrt{n}$. If none of them divide evenly, the number is prime.

Example 2: Is 97 Prime?

$\sqrt{97} \approx 9.85$, so test primes up to $9$: that means $2, 3, 5, 7$.

• $97 \div 2 = 48.5$ — not divisible
• $97 \div 3$: digit sum $= 9 + 7 = 16$, not divisible by $3$
• $97 \div 5 = 19.4$ — not divisible
• $97 \div 7 \approx 13.86$ — not divisible

No prime up to $9$ divides $97$, so $97$ is prime.

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It works by systematically eliminating composite numbers.

How it works (finding primes up to 30):

1. Write out all numbers from $2$ to $30$
2. Circle $2$ (prime). Cross out every multiple of $2$: $4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30$
3. The next uncrossed number is $3$ (prime). Cross out every multiple of $3$ not already crossed: $9, 15, 21, 27$
4. The next uncrossed number is $5$ (prime). Cross out every multiple of $5$ not already crossed: $25$
5. $\sqrt{30} \approx 5.5$, so we stop checking here

Primes up to 30: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$

The sieve is efficient because each step eliminates many composites at once. For finding all primes up to a moderate number (say, $100$ or $200$), it is faster than testing each number individually.

Factor Trees

A factor tree is a diagram that breaks a composite number down into its prime factors step by step. At each level, you split a number into two factors. You keep splitting until every branch ends at a prime.

Example 3: Factor Tree for 60

Start with $60$ and find any factor pair:

$60 = 2 \times 30$

$2$ is prime (stop). Now break down $30$:

$30 = 2 \times 15$

$2$ is prime (stop). Now break down $15$:

$15 = 3 \times 5$

Both $3$ and $5$ are prime (stop).

Reading the primes at the ends of all branches:

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

Example 4: Factor Tree for 72

$72 = 8 \times 9$

Break down $8$:

$8 = 2 \times 4 = 2 \times 2 \times 2 = 2^3$

Break down $9$:

$9 = 3 \times 3 = 3^2$

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

Does the Starting Split Matter?

No. You can start with any factor pair and you will always arrive at the same set of prime factors. This is guaranteed by the fundamental theorem of arithmetic.

For example, starting $72$ differently:

$72 = 2 \times 36 = 2 \times 6 \times 6 = 2 \times (2 \times 3) \times (2 \times 3) = 2^3 \times 3^2$

Same result.

Example 5: Factor Tree for 180

$180 = 10 \times 18$

Break down $10$: $10 = 2 \times 5$

Break down $18$: $18 = 2 \times 9 = 2 \times 3 \times 3$

Combine:

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

Writing Prime Factorization with Exponents

When the same prime appears multiple times, use exponents to write the factorization compactly.

Convention: Write primes in ascending order ($2$ before $3$ before $5$, etc.).

Using Prime Factorization to Find GCF and LCM

Prime factorization makes GCF and LCM calculations straightforward, especially for larger numbers where listing all factors or multiples would be tedious.

GCF: Shared Primes, Smaller Exponents

Example 6: GCF of 84 and 126

$84 = 2^2 \times 3 \times 7$ $126 = 2 \times 3^2 \times 7$

Shared primes: $2$, $3$, $7$.

• $2$: smaller exponent is $2^1$
• $3$: smaller exponent is $3^1$
• $7$: smaller exponent is $7^1$

$\text{GCF}(84, 126) = 2 \times 3 \times 7 = 42$

LCM: All Primes, Larger Exponents

Example 7: LCM of 84 and 126

Using the same factorizations:

• $2$: larger exponent is $2^2$
• $3$: larger exponent is $3^2$
• $7$: larger exponent is $7^1$

$\text{LCM}(84, 126) = 2^2 \times 3^2 \times 7 = 4 \times 9 \times 7 = 252$

Verification using the relationship:

$\text{GCF} \times \text{LCM} = 42 \times 252 = 10{,}584$ $84 \times 126 = 10{,}584 \quad \text{Checks out.}$

The Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states:

Every integer greater than $1$ is either a prime or can be written as a product of primes in exactly one way (ignoring the order of the factors).

This means:

• Existence: Every composite number can be broken into primes
• Uniqueness: There is only one way to do it (the same primes with the same exponents)

For example, $360 = 2^3 \times 3^2 \times 5$ is the only prime factorization of $360$. No matter which factor tree you draw, you always end up with three $2$s, two $3$s, and one $5$.

This uniqueness is what makes prime factorization so powerful — it gives every number a “fingerprint” that you can use reliably for GCF, LCM, and fraction operations.

Real-World Application: Electrician — Wire Bundling

An electrician has three cable runs: one with $24$ wires, one with $36$ wires, and one with $60$ wires. To organize them neatly into the junction box, the electrician wants to bundle wires into equal-sized groups with no wires left over. What is the largest bundle size?

Use prime factorization to find the GCF:

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

Shared primes with smallest exponents:

• $2$: smallest is $2^2 = 4$
• $3$: smallest is $3^1 = 3$

$\text{GCF}(24, 36, 60) = 4 \times 3 = 12$

The electrician bundles wires in groups of 12:

• $24 \div 12 = 2$ bundles
• $36 \div 12 = 3$ bundles
• $60 \div 12 = 5$ bundles

That is $10$ total bundles, all the same size, with no loose wires.

Common Mistakes to Avoid

1. Stopping a factor tree too early. Every branch must end at a prime. $12 = 3 \times 4$ is not complete because $4 = 2 \times 2$. The correct factorization is $12 = 2^2 \times 3$.
2. Calling $1$ a prime. By mathematical convention, $1$ is not prime. Including it in a factorization (like $12 = 1 \times 2^2 \times 3$) is incorrect — the Fundamental Theorem of Arithmetic requires factorization into primes only, and $1$ is not prime.
3. Forgetting to use exponents. Writing $72 = 2 \times 2 \times 2 \times 3 \times 3$ is correct but hard to read. The standard form is $72 = 2^3 \times 3^2$.
4. Mixing up GCF and LCM exponent rules. For GCF, take the smaller exponent of shared primes. For LCM, take the larger exponent of all primes. Swapping these is the single most common error.
5. Thinking different factor trees give different results. The path may differ ($72 = 8 \times 9$ vs $72 = 6 \times 12$), but the final set of primes is always the same.

Practice Problems

Test your understanding with these problems. Click to reveal each answer.

Key Takeaways

• Prime numbers have exactly two factors ($1$ and themselves); composite numbers have more than two
• $2$ is the only even prime, and $1$ is neither prime nor composite
• A factor tree breaks a number into primes by splitting at each level until all branches reach a prime
• Prime factorization with exponents is the standard way to express a number’s prime breakdown (e.g., $72 = 2^3 \times 3^2$)
• The fundamental theorem of arithmetic guarantees that every integer greater than $1$ has a unique prime factorization
• To find the GCF, take shared primes with the smaller exponent; to find the LCM, take all primes with the larger exponent
• Factor trees can start with any factor pair — the final result is always the same

Return to Pre-Algebra for more topics in this section.