The Fundamental Theorem of Arithmetic

Where we are headed#

Every whole num­ber big­ger than $1$ is either prime or can be bro­ken down into primes. You prob­a­bly did this with fac­tor trees in your junior classes. Here we ask how far that idea really goes, and we meet the one word that does the heavy lift­ing: uniquely.

By the end you should be able to write any com­pos­ite num­ber as a prod­uct of prime pow­ers, and explain why nobody else's fac­tori­sa­tion of that num­ber can ever dis­agree with yours.

Build­ing num­bers out of primes#

Start from the primes and mul­ti­ply. Take $2$, $3$, $5$ and $13$, use each as often as you like:

$$3 \times 13 = 39, \qquad 2^2 \times 5 = 20, \qquad 2 \times 3^2 \times 13 = 234$$

Every prod­uct you form this way is a pos­i­tive inte­ger. The more inter­est­ing ques­tion runs the other way: if you start from a num­ber, can you always get back to primes?

Try it with $2340$. Keep pulling out the small­est prime that divides what is left:

$$2340 = 2 \times 1170 = 2 \times 2 \times 585 = 2^2 \times 3 \times 195 = 2^2 \times 3 \times 3 \times 65 = 2^2 \times 3^2 \times 5 \times 13$$

Could this go on for ever? No. Each step makes the num­ber strictly smaller, and a whole num­ber can­not keep shrink­ing for ever while stay­ing above $1$, so the process must stop.

The the­o­rem#

Fun­da­men­tal The­o­rem of Arith­metic. Every com­pos­ite num­ber can be writ­ten as a prod­uct of primes, and that fac­tori­sa­tion is unique apart from the order in which the fac­tors are writ­ten.

Read that sen­tence again, slowly. Two sep­a­rate claims are packed into it, and most stu­dents only notice the first.

Exis­tence: a fac­tori­sa­tion into primes can always be found. That is what the $2340$ cal­cu­la­tion above shows.

Unique­ness: there is only one such fac­tori­sa­tion. Writ­ing $2340 = 2^2 \times 3^2 \times 5 \times 13$ is not a cor­rect answer; it is the answer. Reorder­ing the fac­tors as $13 \times 5 \times 3^2 \times 2^2$ changes noth­ing, because order is not part of what is being claimed.

Unique­ness is what makes the the­o­rem so use­ful. Think of the prime fac­tori­sa­tion as a num­ber's fin­ger­print, or its Aad­haar num­ber: two num­bers with the same prime fac­tori­sa­tion are the same num­ber, and a prime that appears in one fac­tori­sa­tion of $n$ appears in every fac­tori­sa­tion of $n$.

Writ­ing the stan­dard form#

To write it neatly, col­lect equal primes into pow­ers and list them in increas­ing order:

$$n = p_1^{a_1} \, p_2^{a_2} \, \cdots \, p_k^{a_k}, \qquad p_1 < p_2 < \cdots < p_k$$

Now check by mul­ti­ply­ing back: $4 \times 9 = 36$, $36 \times 5 = 180$, $180 \times 49 = 8820$. Please make this a habit. A fac­tori­sa­tion that mul­ti­plies back to the wrong num­ber is the one slip that costs you every mark that fol­lows it.

Two things the the­o­rem lets you decide at a glance#

Whether one num­ber divides another. Take $756 = 2^2 \times 3^3 \times 7$ and $126 = 2 \times 3^2 \times 7$. Every prime in $126$ appears in $756$ with at least as large an expo­nent, so $126$ divides $756$, no long divi­sion needed. Had $126$ car­ried a $3^4$, no amount of arith­metic could have made it divide.

Whether a num­ber can end in $0$. A num­ber ends in zero exactly when it is divis­i­ble by $10 = 2 \times 5$, so its fac­tori­sa­tion must con­tain both a $2$ and a $5$. $3^n \times 7$ never ends in $0$, for any $n$, because no $2$ and no $5$ can appear.

A cau­tion about $1$#

$1$ is not prime, and the the­o­rem is stated for com­pos­ite num­bers. Stu­dents some­times ask why it is left out. Here's why: if $1$ counted as a prime, unique­ness would col­lapse at once, since $12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3$, and every num­ber would have infi­nitely many "dif­fer­ent" fac­tori­sa­tions. So leav­ing out $1$ isn't fussi­ness; it is exactly what keeps the the­o­rem true.

Prac­tice#

1. Write as a prod­uct of prime pow­ers: (a) $3150$, (b) $1024$, (c) $4235$.
2. Does $180$ divide $5400$? Answer using prime fac­tori­sa­tions only, not divi­sion.
3. Can $2^a \times 3^b$ ever end in the digit $5$? Give a rea­son.
4. $n = 2^3 \times 5^2 \times 11$. How many of the num­bers $4$, $22$, $50$, $8$, $121$ divide $n$?
5. A num­ber has exactly three prime fac­tors, all dif­fer­ent, and equals $255$. Find them.

Answers#