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.