Prime Factorization: Free Response

The first split is handed to you, so the tree starts with two branches:

$228 = 4 \times 57.$

Neither branch is finished. $4$ is composite, and so is $57$: its digit sum is $5 + 7 = 12$, a multiple of $3$, so $3$ divides it. Split each one:

$4 = 2 \times 2, \qquad 57 = 3 \times 19.$

Now look at the four numbers left at the ends: $2$, $2$, $3$ and $19$. None of them has a factor pair other than $1$ and itself, so no branch can be split again and the tree is complete. Reading the ends from left to right,

$228 = 2 \times 2 \times 3 \times 19.$

Multiplying them back is the check: $2 \times 2 = 4$, then $4 \times 3 = 12$, then $12 \times 19 = 228$.

Prime-power form collects the equal primes together. The tree produced two copies of $2$, one $3$ and one $19$, and an exponent is nothing more than a count of copies:

$2 \times 2 = 2^2.$

The $3$ and the $19$ each appear once, and a prime that appears once is written with no exponent at all, since one copy is what that means. Listing the primes from smallest to largest,

$228 = 2^2 \times 3 \times 19.$

Expanding the power back out checks the bookkeeping: $2^2 = 4$, and $4 \times 3 \times 19 = 228$, the number the tree started from. Nothing was gained or lost in the rewrite; prime-power form is the same product written more briefly.

Any genuine split will do, so start with one you can see. Taking $350 = 35 \times 10$, both branches are composite and both split once more:

$35 = 5 \times 7, \qquad 10 = 2 \times 5.$

Every number at the end of a branch is now prime, so the tree is finished. The ends are $5$, $7$, $2$ and $5$, and collecting the two copies of $5$ into a power gives

$350 = 2 \times 5^2 \times 7.$

What tells you a branch is finished is the number sitting on it, not the shape of the tree. A composite number has a factor pair with both factors bigger than $1$, so it can always be split again; a prime has no such pair, so it cannot. Every number on a tree is bigger than $1$, because $1 \times n$ is not a genuine split, so each branch ends exactly when its number is prime.

The number ends in $0$, so it is even and $2$ divides it:

$2{,}250 \div 2 = 1{,}125.$

Now $1{,}125$ is odd, so $2$ is finished. Its digit sum is $1 + 1 + 2 + 5 = 9$, a multiple of $3$, so $3$ divides it, and the digit sum of the quotient, $3 + 7 + 5 = 15$, says that $3$ divides that too:

$1{,}125 \div 3 = 375, \qquad 375 \div 3 = 125.$

The digit sum of $125$ is $8$, not a multiple of $3$, so $3$ is finished. It ends in $5$, so $5$ divides it, and it does so three times over:

$125 \div 5 = 25, \qquad 25 \div 5 = 5, \qquad 5 \div 5 = 1.$

The quotient has reached $1$, so the column is closed. The divisors used, in the order they were used, were $2$, $3$, $3$, $5$, $5$ and $5$, so collecting the repeats,

$2{,}250 = 2 \times 3^2 \times 5^3.$

As a check, $3^2 = 9$ and $5^3 = 125$, so $2 \times 9 = 18$ and $18 \times 125 = 2{,}250$.

Rule out the small primes with the digit tests rather than by dividing. The number is odd, so $2$ is out. Its digit sum is $3 + 9 + 1 = 13$, not a multiple of $3$, so $3$ is out. It ends in neither $0$ nor $5$, so $5$ is out.

That leaves the primes above $5$, tried in turn. $7 \times 55 = 385$ and $7 \times 56 = 392$, so $7$ misses. $11 \times 35 = 385$ and $11 \times 36 = 396$, so $11$ misses. $13 \times 30 = 390$, one short, so $13$ misses. Then comes $17$:

$391 \div 17 = 23.$

Now factor the quotient. Is $23$ prime? $4 \times 4 = 16$ is under it and $5 \times 5 = 25$ is past it, so only $2$ and $3$ need testing, and neither divides it. Both factors are prime, so the column is done:

$391 = 17 \times 23.$

The stopping rule bounds how much work this could ever have been. A prime $p$ is worth testing only while $p \times p$ is no bigger than the number: $19 \times 19 = 361$ is under $391$, while $23 \times 23 = 529$ is past it. So $19$ was the last candidate, and if none of $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$ had divided the number, it would have been prime itself.

The arithmetic is sound: $2 \times 27 = 54$ and $54 \times 13 = 702$. But multiplying back to the right number is only one of the two things a prime factorization has to do. The other is that every factor written down is prime, and $27$ is not: it is $3 \times 9$, and the $9$ splits again.

Carry that branch down:

$27 = 3 \times 3 \times 3 = 3^3.$

So the repair is to replace the composite factor by its own primes and leave everything else alone:

$702 = 2 \times 3^3 \times 13.$

Repeated division arrives at the same place from the other end. The number is even, so $702 \div 2 = 351$; the digit sum of $351$ is $9$, so $351 \div 3 = 117$, then $117 \div 3 = 39$, then $39 \div 3 = 13$, which is prime.

The general point is worth keeping. Any product that multiplies back to the number is a factorization of it, and a number has many of those. Only a product built entirely from primes is the prime factorization, and that is the one the theorem promises there is just one of, apart from the order in which the factors are written.

A pallet is $6$ crates of $15$ boxes of $14$ cookies, so the count is the product $6 \times 15 \times 14$. That product is a factor tree already in progress: its first splits have been handed to you, and each of the three counts is composite, so each splits once more:

$6 = 2 \times 3, \qquad 15 = 3 \times 5, \qquad 14 = 2 \times 7.$

Every branch now ends in a prime. Pooling the six of them and collecting the repeats,

$6 \times 15 \times 14 = 2 \times 3 \times 3 \times 5 \times 2 \times 7 = 2^2 \times 3^2 \times 5 \times 7.$

For the count itself, multiply the powers out: $4 \times 9 = 36$, then $36 \times 5 = 180$, then $180 \times 7 = 1{,}260$ cookies on a pallet. Multiplying the container counts directly agrees: $15 \times 14 = 210$ and $6 \times 210 = 1{,}260$.

Four pallets hold four times as many cookies as one, so the total is $4$ multiplied by a pallet's worth. The factorization does not have to be started again: $4$ is not prime, and its own factorization is

$4 = 2 \times 2.$

So the order adds two more copies of $2$ to the primes a single pallet already contributed, and touches nothing else:

$2^4 \times 3^2 \times 5 \times 7.$

The exponent on the $2$ grows because an exponent counts copies, and two more copies have joined the pile. Multiplying out, $16 \times 9 = 144$, then $144 \times 5 = 720$, then $720 \times 7 = 5{,}040$ cookies in the order.

The two calculations are the same tree entered at different points.

The product of the three counts is the number of cookies on a pallet, so writing that number as $6 \times 15 \times 14$ is a legitimate way to start its factor tree. Three branches instead of two, but every one of them still has to be carried down. Factoring each count and pooling what falls out is nothing more than finishing those branches:

$6 \times 15 \times 14 = (2 \times 3) \times (3 \times 5) \times (2 \times 7).$

Multiplying first and then factoring starts the same number from the top with some other first split, and it also stops only when every branch holds a prime.

That the two agree is not luck, and it is not something to be checked case by case. The Fundamental Theorem of Arithmetic says that a whole number greater than $1$ has exactly one prime factorization, apart from the order in which the factors are written. Both calculations end in a product of primes equal to the same number, so they must end in the same collection of primes, differing at most in the order they were produced.

Start from the split she was given and finish every branch:

$780 = 4 \times 195.$

The branch holding $4$ is composite, and $4 = 2 \times 2$. The branch holding $195$ is composite too: it ends in $5$, so $5$ divides it, giving $195 = 5 \times 39$, and then $39 = 3 \times 13$.

Every branch now ends in a prime, and the ends are $2$, $2$, $5$, $3$ and $13$. Collecting the repeat and putting the primes in order,

$780 = 2^2 \times 3 \times 5 \times 13.$

Checking: $4 \times 3 = 12$, then $12 \times 5 = 60$, then $60 \times 13 = 780$.

His first branch is finished in one step, since $6 = 2 \times 3$. The other is not: $130$ ends in $0$, so $130 = 2 \times 65$, and then $65 = 5 \times 13$. The ends of his tree are $2$, $3$, $2$, $5$ and $13$.

Compare the two collections by counting copies rather than by reading positions. Sorted, Maya's ends are $2$, $2$, $3$, $5$, $13$ and Ravi's are $2$, $2$, $3$, $5$, $13$: two copies of $2$ and one each of $3$, $5$ and $13$ on both sides. So both trees deliver

$780 = 2^2 \times 3 \times 5 \times 13.$

What does differ is the route. Maya's tree passed through $4$, $195$ and $39$; Ravi's passed through $6$, $130$ and $65$. Not one of those intermediate numbers survives into the answer, which is the first sign that the route is not part of the result.

Take the objection in two steps.

First, look at what the two lines actually are. In $4 \times 195$ every factor is composite, and the same is true of $6 \times 130$. Each is a factorization of $780$ in the loose sense that it multiplies back to $780$, but neither is a prime factorization, because a prime factorization is a product in which every factor is prime. They are not two answers; they are two unfinished starts. Products of that loose kind are plentiful, and nobody claims otherwise: $780$ is also $10 \times 78$, and $20 \times 39$, and $2 \times 390$.

Second, the finished trees. Both of them ended at

$780 = 2^2 \times 3 \times 5 \times 13,$

which is what the Fundamental Theorem of Arithmetic requires: every whole number greater than $1$ has exactly one prime factorization, apart from the order in which the factors are written.

The reason a first split cannot matter is that a split only decides which branch a prime comes down. It cannot invent a prime the number does not have, since everything on the tree multiplies back to the number at every stage, and it cannot lose one, since no branch is abandoned before it holds a prime and nothing is thrown away along the way. So whatever route is taken, the finished tree is a product of primes equal to $780$, and the theorem says there is only one of those.

Two phrases are missing, and each is missing for its own reason.

Which numbers it covers. Every prime is at least $2$, so any product of primes is at least $2$ as well. No product of primes can therefore equal $1$ or $0$, and the sentence has to be restricted to whole numbers greater than $1$. The number $1$ is the case that bites in practice: it has no prime factor at all, because every prime is larger than $1$ itself, so there is nothing for a factorization of it to be built from.

In what sense it is unique. Take $110$. It can be written

$110 = 2 \times 5 \times 11 \qquad \text{and} \qquad 110 = 11 \times 5 \times 2,$

and a reader who counts those as two different prime factorizations has just contradicted the uncorrected sentence. They are the same collection of primes written in a different order, so what the theorem claims is uniqueness apart from order. That is also why prime-power form conventionally lists the primes from smallest to largest: fixing the order makes the one answer look like one answer.

Put together: every whole number greater than $1$ has exactly one prime factorization, apart from the order in which the factors are written.

The number is even, so $34 = 2 \times 17$, and $17$ is prime. That is the one factorization the theorem promises.

Now suppose $1$ counted as a prime. Multiplying by $1$ changes nothing, so every one of

$34 = 1 \times 2 \times 17 = 1 \times 1 \times 2 \times 17 = 1 \times 1 \times 1 \times 2 \times 17$

would be a product of "primes" equal to $34$, and the list never ends, because another copy of $1$ can always be pushed in. Uniqueness would not merely be dented in an odd case; it would fail for every number at once, and "the" prime factorization would be a phrase with no meaning behind it.

Keeping $1$ out costs nothing, since $1$ contributes nothing to a product, and it buys back the single answer the theorem is about. That is the bookkeeping reason mathematicians do not count $1$ as prime, and it is why a factorization is built only out of numbers that are at least $2$.

The first claim. Suppose two numbers have the same prime factorization. A factorization is a product, and a product of one fixed collection of numbers has one value, so each of the two numbers equals that value and they are equal to each other. Notice that this direction does not even need the theorem; it is ordinary multiplication.

The theorem is what makes the reverse direction work: one number cannot present two genuinely different prime factorizations, because apart from the order of the factors there is only one to have. Taken together, the two directions are what let a prime factorization be called a fingerprint. It names one number and no other.

The weakened version. Now only the primes that appear are compared, and how many times each appears is thrown away. That is not enough to pin a number down:

$44 = 2^2 \times 11 \qquad \text{and} \qquad 242 = 2 \times 11^2.$

Both use the primes $2$ and $11$ and no others, and the two numbers are plainly different. One such pair is all it takes to retire the weakened claim.

The gap between the two claims is exactly what an exponent records. A prime factorization says which primes appear and how many copies of each; a bare list of the primes keeps only the first half, and it is the second half that tells these two numbers apart.