Math 6

Every number has exactly one prime factorization

Two people break the same number into primes, starting in different places. Must they end with the same primes?

You need

Prime factorizationMath 6

Unlocks

Proof by contradictionGeometry

Where you are 10 in Divisibility and primes

Number9

Divisibility and primes10

▴ 5 above Prime factorization Tests for three and nine The sieve of Eratosthenes

Every number has exactly one prime factorization

Greatest common factor and least common multiple4

Why this exists

Chiara is a locksmith with an unusual system. Every key she cuts has a code number, and the code says how to cut it: write the code as a product of primes, then cut one notch for each prime, as deep as that prime, shallowest first. Code 140 is 2 \cdot 2 \cdot 5 \cdot 7, so its key has four notches, of depths 2, 2, 5 and 7.

Her apprentices, Kofi and Anika, are both asked to cut code 140. Kofi starts with 140 = 10 \cdot 14; Anika starts with 140 = 4 \cdot 35. Each keeps splitting until only primes are left, as a factor tree does, and Figure 1 shows what they find: the same four primes.

The system only works if that always happens. If one code could break into two different lists of primes, two apprentices could cut two different keys from one code.

Definition

A prime factorization of a whole number n greater than 1 writes n as a product of prime numbers. A prime is its own factorization: the factorization of 7 is just 7. Repeats are allowed and they count, so 2 \cdot 2 \cdot 5 \cdot 7 and 2 \cdot 5 \cdot 7 are different factorizations, of 140 and of 70.

Two factorizations are the same when they use the same primes, each the same number of times, in any order: 2 \cdot 5 \cdot 2 \cdot 7 and 7 \cdot 2 \cdot 2 \cdot 5 are one factorization written two ways. The tidy form lists the primes from smallest to largest and gathers repeats into powers:

140 = 2^2 \cdot 5 \cdot 7

The claim of this lesson is that every whole number above 1 has exactly one prime factorization. “Exactly one” is two claims in one:

at least one (existence): the number can be broken into primes at all;
at most one (uniqueness): however you break it, you reach the same primes, each the same number of times.

Intuition

Figure 1Different first splits, the same primes at the bottom.

Primes are the pieces that cannot be split any further, so a prime factorization lists a number’s smallest building blocks. A different first split only groups the blocks differently on the way down: Kofi’s 10 and 14 and Anika’s 4 and 35 hold the same 2, 2, 5 and 7.

That picture quietly assumes what we want to show, that a number is made of one fixed set of blocks. Why it is true shows a number system where the same picture fails.

Results

The fundamental theorem of arithmetic. Every whole number greater than 1 can be written as a product of primes, and in only one way apart from the order of the factors.

It rests on one fact about primes, the prime divisor property: if a prime divides a product of whole numbers (goes into it with nothing left over), it divides at least one of the factors. For example, 7 divides 14 \cdot 9 = 126, and it divides 14. A number that is not prime has no such guarantee: 6 divides 4 \cdot 9 = 36 but divides neither 4 nor 9.

Three consequences you will use:

Divisors can be read off. A whole number d above 1 divides n exactly when every prime of d appears in the factorization of n at least as many times as in d. So 28 = 2^2 \cdot 7 divides 140 = 2^2 \cdot 5 \cdot 7, and 8 = 2^3 does not.
Squares have even powers. A whole number above 1 is a perfect square exactly when every power in its prime factorization is even.
Different factorizations, different numbers. If two products of primes differ in any prime or in any count, they are different numbers, and you can say so without multiplying.

Each needs uniqueness: only uniqueness makes a factorization the list, so that a prime missing from it is missing from the number.

Why it is true

At least one factorization. Take a whole number above 1. If it is prime, it is its own factorization. If not, it is a product of two smaller whole numbers, each above 1. Split each of those that is not prime, and keep going. Every split gives smaller numbers, and whole numbers above 1 cannot keep getting smaller for ever, so the splitting stops, and it can only stop when every piece is prime. That argument is complete; the one thing it takes for granted is that a chain of ever smaller whole numbers must end.

At most one, given the prime divisor property. Suppose a number had two prime factorizations,

p_1 \cdot p_2 \cdots p_r = q_1 \cdot q_2 \cdots q_s

with every p and every q prime. The prime p_1 divides the left side, so it divides the right side, a product of qs. By the prime divisor property it divides one of them, say q_j. But q_j is prime, so its only divisors are 1 and itself, and p_1 \ne 1, so p_1 = q_j. Divide both sides by that prime: two shorter lists are left, still with equal products. Each round removes one matching pair. When one side runs out its product is 1, and a product of primes is never 1, so the other side runs out at the same moment. The two lists matched prime for prime: they were the same factorization.

What was not proved. That argument leaned on the prime divisor property, which was stated, not proved. It is true for whole numbers. Euclid’s Elements proves it for a product of two numbers (Book VII, Proposition 30), and repeating that covers longer products; the usual modern proof uses a tool that comes later, Bezout’s identity. So existence is proved here in full; uniqueness is proved here from the prime divisor property, which is assumed.

Why it needs proving at all. Imagine a world that has only the even numbers 2, 4, 6, 8, \ldots Two even numbers multiply to an even number, so this world has its own multiplication. Call an even number an even-prime if it is not a product of two even numbers. A product of two even numbers is always a multiple of 4, so the even-primes are exactly the even numbers that are not multiples of 4:

2,\ 6,\ 10,\ 14,\ 18,\ 22,\ 26,\ 30,\ \ldots

Now factor 140 in this world:

140 = 10 \cdot 14 = 2 \cdot 70

All of 2, 10, 14 and 70 are even-primes, so 140 has two different factorizations into even-primes. Existence still holds there (the splitting argument works unchanged); uniqueness breaks. And the prime divisor property is exactly what is missing: in this world the even-prime 2 divides 10 \cdot 14, because 10 \cdot 14 = 2 \cdot 70, yet it divides neither 10 nor 14, since 10 = 2 \cdot 5 and 14 = 2 \cdot 7 and neither 5 nor 7 is in the world. If Chiara’s codes lived there, code 140 could cut two different keys.

So uniqueness is not a law of multiplication in general. It is a special fact about the whole numbers, and the prime divisor property is where it lives.

Worked examples

Example 1

Two apprentices, one code

Kofi and Anika are given code 198. Kofi starts with 198 = 18 \cdot 11 and Anika with 198 = 6 \cdot 33. Finish both factorizations and compare.

Solution

Kofi: 11 is prime, and 18 = 2 \cdot 9 = 2 \cdot 3 \cdot 3, so he reaches 2 \cdot 3 \cdot 3 \cdot 11.

Anika: 6 = 2 \cdot 3 and 33 = 3 \cdot 11, all primes, so she reaches 2 \cdot 3 \cdot 3 \cdot 11.

The same four primes, in tidy form 198 = 2 \cdot 3^2 \cdot 11. The theorem said they had to agree; working both out confirms it here. Check. 2 \cdot 9 \cdot 11 = 198.

Example 2

Equal or not, without multiplying

Lars has two key tags, 2^3 \cdot 3^2 \cdot 7 and 2^2 \cdot 3^3 \cdot 7. Do they name the same code?

Solution

Both are products of primes, so each is a prime factorization of the number it equals. The first has three 2s and the second has two. If the two numbers were equal, that one number would have two different prime factorizations, which uniqueness rules out. So they are different codes.

Check. 8 \cdot 9 \cdot 7 = 504 and 4 \cdot 27 \cdot 7 = 756.

Example 3

Reading divisors off a factorization

A code is 1176 = 2^3 \cdot 3 \cdot 7^2. Decide, without dividing, whether 12, 9 and 5 divide 1176.

Solution

12 = 2^2 \cdot 3. The factorization of 1176 has three 2s, at least the two needed, and a 3. Taking those out leaves 2 \cdot 7^2 = 98, so 1176 = 12 \cdot 98 and 12 divides it.

9 = 3^2 needs two 3s, and 1176 has one. Suppose 9 did divide 1176, say 1176 = 9 \cdot k. Factorizing k and writing 3 \cdot 3 in front would give a prime factorization of 1176 with at least two 3s. That differs from 2^3 \cdot 3 \cdot 7^2, and uniqueness forbids a second factorization. So 9 does not divide 1176.

5 is not in the factorization at all, and the same argument shows 5 does not divide 1176.

Check. 1176 \div 12 = 98, 1176 \div 9 = 130 remainder 6, and 1176 \div 5 = 235 remainder 1.

Example 4

Is the code a perfect square?

Noor wants a code that is a perfect square. Is 3600 = 2^4 \cdot 3^2 \cdot 5^2 one? Is 300 = 2^2 \cdot 3 \cdot 5^2?

Solution

Squaring a number doubles every power in its factorization, because each prime appears once in each copy. Halving the powers of 3600 gives 2^2 \cdot 3 \cdot 5 = 60, and (2^2 \cdot 3 \cdot 5)^2 = 2^4 \cdot 3^2 \cdot 5^2, so 3600 = 60^2.

For 300, suppose 300 = m^2 for some whole number m. Factorize m; then m \cdot m is a prime factorization of 300 in which every power is even. By uniqueness it must be the one we have, 2^2 \cdot 3 \cdot 5^2, but there the power of 3 is odd. So no whole number squares to 300.

Check. 17^2 = 289 and 18^2 = 324, and 300 lies strictly between them.

Example 5

When a prime divides a product

Sebastián’s code is 13 \cdot 22 \cdot 15. Does 7 divide it? Does 6?

Solution

7 is prime and divides none of 13, 22 and 15. If it divided their product, the prime divisor property would make it divide one of them. So 7 does not divide 13 \cdot 22 \cdot 15.

6 is not prime, so that shortcut is not allowed, and here it would give the wrong answer. 6 divides none of the three factors, yet the product is 13 \cdot (2 \cdot 11) \cdot (3 \cdot 5), whose factorization 2 \cdot 3 \cdot 5 \cdot 11 \cdot 13 contains a 2 and a 3. So 6 divides it: 13 \cdot 22 \cdot 15 = 4290 = 6 \cdot 715.

Check. 4290 \div 7 = 612 remainder 6.

Example 6

Three ways in the even world

In the even-number world of Why it is true, find every factorization of 180 into even-primes.

Solution

A product of three or more even numbers is a multiple of 8, and 180 is not, so every factorization here has exactly two factors. The factor pairs of 180 in which both numbers are even are

180 = 2 \cdot 90 = 6 \cdot 30 = 10 \cdot 18

None of 2, 90, 6, 30, 10 and 18 is a multiple of 4, so all are even-primes, and 180 has three different factorizations in this world.

The reason shows in 180 = 2^2 \cdot 3^2 \cdot 5. Each even-prime is 2 times an odd number, so each factor takes one 2, and the odd part 3 \cdot 3 \cdot 5 can be shared between them in three ways.

Boundaries

1 is left out. It contains no primes, so it has no prime factorization. This is also why 1 is not called prime: if it were, 6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3 would be different factorizations, and no number would have exactly one. Prime and composite numbers has the rest of that story.

0 has none. No product of primes equals 0.

Order does not count. 2 \cdot 3 \cdot 5 and 5 \cdot 3 \cdot 2 are the same factorization. “Exactly one” means one apart from order, never one written form.

Only primes count. 4 \cdot 9 \cdot 5 and 2 \cdot 18 \cdot 5 are both 180, but neither is a prime factorization. Uniqueness is a promise about the end of the splitting, not the middle.

Unique does not mean easy to find. The theorem says nothing about how long finding the factorization takes, and for numbers hundreds of digits long nobody knows a fast way.

It depends on the number system. The even-number world loses uniqueness, and so do the numbers 1, 5, 9, 13, \ldots that leave remainder 1 when divided by 4 (Exercises 20 and 21). The theorem is about the whole numbers.

Where this goes next

Because the list is fixed, two numbers can be compared prime by prime, and that is how the GCF and LCM are found from prime factorizations.

The even-powers test for squares goes further. Counting primes on each side of an equation, as Example 4 did for 300, is how proof by contradiction shows that \displaystyle \sqrt{2} and \displaystyle \sqrt{3} are not fractions, which opens the door to irrational numbers.

The prime divisor property, assumed here, is usually proved from Bezout’s identity, which comes from running the Euclidean algorithm backwards, and introductory number theory builds on this theorem from its first page.

Exercises

Same code, different start

Kofi factorizes 180 starting from 12 \cdot 15, and Anika starting from 20 \cdot 9. Finish both and compare.
Finish the factorization of 468 starting from 4 \cdot 117, and again starting from 18 \cdot 26.
Finish the factorization of 1001 starting from 7 \cdot 143, and again starting from 11 \cdot 91.

Equal or not, without multiplying

Decide whether the two products name the same number. Give the reason before any arithmetic.

2^4 \cdot 5 and 2^2 \cdot 5^2
3 \cdot 7 \cdot 11 and 11 \cdot 3 \cdot 7
2^2 \cdot 3^2 \cdot 5 and 6^2 \cdot 5
2^3 \cdot 3 \cdot 5^2 and 2^2 \cdot 3^2 \cdot 5^2

Reading the factorization

Chiara’s code is n = 2^2 \cdot 3^3 \cdot 7. Decide whether each number divides n. If it does, write n divided by it as a product of primes.

Squares

Is 2^2 \cdot 3^4 \cdot 11^2 a perfect square? If so, of what number?
Is 2^4 \cdot 5^3 a perfect square? What is the smallest whole number you could multiply it by to make one?
540 = 2^2 \cdot 3^3 \cdot 5. Find the smallest whole number that 540 can be multiplied by to give a perfect square, and the square root of the result.

Primes dividing products

Does 11 divide 24 \cdot 35 \cdot 6? Answer without multiplying, then check.
6 divides 10 \cdot 9 but divides neither 10 nor 9. Explain why this does not contradict the prime divisor property.

Other number worlds

List the even-primes up to 30 in the even-number world.
Find two different factorizations of 84 into even-primes.
In the world of the numbers 1, 5, 9, 13, 17, \ldots (those leaving remainder 1 when divided by 4), call a number above 1 a four-prime if it is not a product of two smaller numbers above 1 from that list. Show that 9, 21 and 49 are four-primes, and that 441 = 9 \cdot 49 = 21 \cdot 21 gives 441 two different factorizations into four-primes.
In the same world, show that 693 has two different factorizations into four-primes. (Try starting with 9 and with 21.)

Explaining

Lars says 4 \cdot 9 \cdot 5 and 2 \cdot 18 \cdot 5 are two prime factorizations of 180, so the theorem is false. What is wrong?
Use the theorem to explain why 1 is not counted as a prime.
Can a power of 5, such as 5^{10}, ever end in the digit 0? Explain.
Anika says that if a prime p divides a^2, where a is a whole number above 1, then p divides a. Explain why, using the prime factorization of a.

Answers

Both reach 180 = 2^2 \cdot 3^2 \cdot 5: 12 \cdot 15 = (2 \cdot 2 \cdot 3)(3 \cdot 5) and 20 \cdot 9 = (2 \cdot 2 \cdot 5)(3 \cdot 3).
468 = 2^2 \cdot 3^2 \cdot 13 both ways: 4 \cdot 117 = (2 \cdot 2)(3 \cdot 3 \cdot 13) and 18 \cdot 26 = (2 \cdot 3 \cdot 3)(2 \cdot 13).
1001 = 7 \cdot 11 \cdot 13 both ways, since 143 = 11 \cdot 13 and 91 = 7 \cdot 13.
Different: four 2s against two. (They are 80 and 100.)
Same: the same primes once each, only the order differs. (Both are 231.)
Same: 6^2 \cdot 5 is not yet a prime factorization, and splitting 6^2 = 2^2 \cdot 3^2 turns it into 2^2 \cdot 3^2 \cdot 5. (Both are 180.)
Different: three 2s against two. (They are 600 and 900.)
Yes: 4 = 2^2 needs two 2s and n has two. n \div 4 = 3^3 \cdot 7 = 189.
No: 8 = 2^3 needs three 2s and n has only two.
Yes: 21 = 3 \cdot 7. n \div 21 = 2^2 \cdot 3^2 = 36.
No: 10 = 2 \cdot 5, and 5 is not in the factorization of n.
Yes: 108 = 2^2 \cdot 3^3. n \div 108 = 7.
Yes, every power is even: it is (2 \cdot 3^2 \cdot 11)^2 = 198^2 = 39204.
No, the power of 5 is odd. Multiply by 5: 2^4 \cdot 5^4 = 10000 = 100^2.
Multiply by 15: 540 \cdot 15 = 2^2 \cdot 3^4 \cdot 5^2 = 8100 = 90^2. The powers of 3 and 5 are odd, so any square multiple needs at least one more 3 and one more 5.
No: 11 is prime and divides none of 24, 35 and 6. Check: 24 \cdot 35 \cdot 6 = 5040, and 5040 \div 11 = 458 remainder 2.
The property is about primes, and 6 = 2 \cdot 3 is not prime. Each of its primes does divide a factor, 2 divides 10 and 3 divides 9, but they divide different factors.
2, 6, 10, 14, 18, 22, 26, 30: the even numbers that are not multiples of 4.
84 = 2 \cdot 42 = 6 \cdot 14. None of 2, 42, 6, 14 is a multiple of 4, so all are even-primes.
9 = 3 \cdot 3, 21 = 3 \cdot 7 and 49 = 7 \cdot 7, and their only splits into two factors above 1 use 3 or 7, which leave remainder 3 when divided by 4 and so are not in the list. 9 \cdot 49 = 441 and 21 \cdot 21 = 441, and 441 = 4 \cdot 110 + 1 is in the list.
693 = 9 \cdot 77 = 21 \cdot 33. Here 77 = 7 \cdot 11 and 33 = 3 \cdot 11 split only into numbers leaving remainder 3, so both are four-primes, and so are 9 and 21 (Exercise 20).
4, 9 and 18 are not prime, so neither product is a prime factorization. Splitting them finishes both as 2^2 \cdot 3^2 \cdot 5, one factorization.
If 1 were prime, any factorization could take extra 1s, as in 6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3, so no number would have exactly one.
No. Ending in 0 means being divisible by 10 = 2 \cdot 5, so 2 would divide it. The prime factorization of 5^{10} is ten 5s with no 2, and by uniqueness there is no other, so 2 does not divide it.
If a = p_1 \cdots p_r, then a^2 = (p_1 \cdots p_r)(p_1 \cdots p_r) uses exactly the primes of a, each twice as often. Since p divides a^2, the argument of Example 3 puts p in the factorization of a^2, so p is one of the primes of a, and p divides a.