# Fundamental Theorem of Arithmetic

make Num­ber The­ory a par­ent of this

The Fun­da­men­tal The­o­rem of Arith­metic states that ev­ery nat­u­ral num­ber (greater than or equal to $$2$$) may be ex­pressed as a product of prime num­bers, and the product is unique up to re­order­ing.

This the­o­rem is one of the main rea­sons $$1$$ is not con­sid­ered to be prime: in­deed, if it were prime then $$3 \times 5$$ could be fac­torised into primes as $$3 \times 5 \times 1$$, but these would be two differ­ent fac­tori­sa­tions of the num­ber $$15$$. The FTA’s state­ment is much cleaner if $$1$$ is not thought of as prime.

In a more gen­eral con­text, the FTA says pre­cisely that the ring $$\mathbb{Z}$$ is a unique fac­tori­sa­tion do­main; there is there­fore a much more ab­stract proof than the el­e­men­tary one we will pre­sent fur­ther on in this ar­ti­cle:

• $$\mathbb{Z}$$ is a Eu­clidean do­main (with Eu­clidean func­tion given by “take the mod­u­lus”);

• There­fore $$\mathbb{Z}$$ is a prin­ci­pal ideal do­main (proof);

• And prin­ci­pal ideal do­mains are unique fac­tori­sa­tion do­mains (proof).

# Examples

• The FTA does not talk about $$0$$ or $$1$$; this is be­cause these num­bers are con­ven­tion­ally con­sid­ered nei­ther prime nor com­pos­ite.

• Even if we haven’t both­ered to calcu­late $$17 \times 23 \times 23$$, we can im­me­di­ately say that it is odd. In­deed, by the FTA, $$2$$ can­not di­vide $$17 \times 23^2$$, be­cause the com­plete list of prime fac­tors of this num­ber is $$\{ 17, 23, 23\}$$, and $$2$$ is prime.

# Proof

Ti­mothy Gow­ers has an ex­cel­lent ar­ti­cle about the proof of the FTA.

The FTA con­sists of two parts: we must show that ev­ery num­ber can be de­com­posed as primes, and also that ev­ery num­ber can be de­com­posed uniquely.

## Every num­ber can be writ­ten as a product of primes

This part is the eas­ier, and it uses strong in­duc­tion (a ver­sion of proof by in­duc­tion).

Clearly $$2$$ can be writ­ten as a product of primes, be­cause it is prime; so it can be writ­ten as just it­self.

Now, for $$n$$ big­ger than $$2$$, if $$n$$ is prime then we are im­me­di­ately done (just write it as it­self). Other­wise, $$n$$ is not prime, so it can be writ­ten as $$a \times b$$, say, with $$a$$ and $$b$$ both less than $$n$$.

But by the in­duc­tive hy­poth­e­sis, we can ex­press $$a$$ and $$b$$ each as prod­ucts of primes, so we can ex­press $$n$$ as the com­bined product of the two sets of fac­tors of $$a$$ and $$b$$.

Con­sider $$n = 1274$$. We have two op­tions: $$n$$ is prime or $$n$$ is com­pos­ite.

It turns out that $$n$$ is ac­tu­ally equal to $$49 \times 26$$, so it’s not prime.

By the in­duc­tive hy­poth­e­sis, we can fac­tor $$49$$ as a product of primes (in­deed, it’s $$7^2$$); and we can fac­tor $$26$$ as a product of primes (in­deed, it’s $$2 \times 13$$); so we can fac­tor $$1274$$ as $$2 \times 7^2 \times 13$$.

(If you like, you can view this as just “start again at $$49$$ in­stead of at $$1274$$, and spit out what you get; then start again at $$26$$ in­stead of $$1274$$, and spit out what you get; and fi­nally com­bine the spit­tings-out”; no men­tion of a spooky “in­duc­tive hy­poth­e­sis” at all.)

Note that at this point, we haven’t any guaran­tee at all that this is the only prime fac­tori­sa­tion; all we as­sert so far is that it is a prime fac­tori­sa­tion. <div><div>

## Every num­ber can be de­com­posed uniquely as a product of primes

For this, we will need a ba­sic (but non-ob­vi­ous and im­por­tant) fact about the be­havi­our of prime num­bers: Eu­clid’s lemma, which states that if a prime $$p$$ di­vides a product $$ab$$, then $$p$$ di­vides at least one of $$a$$ and $$b$$.

We will work by in­duc­tion on $$n$$ again. If $$n = 2$$ then the re­sult is im­me­di­ate: a num­ber can only be di­vided by num­bers which are not larger than it, but $$1$$ and $$2$$ are the only such num­bers.

Sup­pose $$n$$ can be writ­ten as both $$p_1 p_2 \dots p_r$$ and $$q_1 q_2 \dots q_s$$, where each $$p_i$$ and $$q_j$$ is prime (but there might be re­peats: maybe $$p_1 = p_2 = q_3 = q_7$$, for in­stance). We need to show that $$r=s$$ and that (pos­si­bly af­ter re­order­ing the lists) $$p_i = q_i$$ for each $$i$$.

Cer­tainly $$p_1$$ di­vides $$n$$, be­cause it di­vides $$p_1 p_2 \dots p_r$$. There­fore it di­vides $$q_1 q_2 \dots q_s$$, and hence it di­vides one of $$q_1$$ or $$q_2 \dots q_s$$, by Eu­clid’s lemma. There­fore ei­ther it di­vides $$q_1$$, or it di­vides one of $$q_2$$ or $$q_3 \dots q_s$$; by in­duc­tion, $$p_1$$ di­vides some $$q_i$$. Be­cause we don’t care about the or­der­ing of the list, let us re­order the list if nec­es­sary so that in fact $$i=1$$: put the fac­tor $$q_i$$ at the start of the list.

Now, $$q_1$$ is prime, and $$p_1$$ is not equal to $$1$$ but it di­vides $$q_1$$; hence $$p_1 = q_1$$.

Di­vid­ing through by $$p_1$$, then, we ob­tain $$p_2 \dots p_r = q_2 \dots q_s$$, a strictly smaller num­ber; so by the in­duc­tive hy­poth­e­sis, $$r-1 = s-1$$ (so $$r=s$$) and the un­ordered list of $$p_i$$ is the same as the un­ordered list of $$q_i$$ for $$i \geq 2$$.

This proves the the­o­rem.

# Why is this not ob­vi­ous?

Ti­mothy Gow­ers has a good piece on why this re­sult is not just ob­vi­ous. Of course, what is “ob­vi­ous” and what is not “ob­vi­ous” varies heav­ily de­pend­ing on who you’re talk­ing to. For this au­thor per­son­ally, the true rea­son it’s not ob­vi­ous is Gow­ers’s rea­son num­ber 4: be­cause there are very similar struc­tures which do not have the prop­erty of unique fac­tori­sa­tion. (Gow­ers uses $$\mathbb{Z}[\sqrt{-5}]$$; on the page on ir­re­ducibles, we show that $$\mathbb{Z}[\sqrt{-3}]$$ could be used just as well.)

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.