Monthly Archives: April 2017

April 5, 2017 · 11:40 am

A different proof of the fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer can be uniquely written as a product of primes (i.e. \mathbb{Z} is a unique factorisation domain).

The usual proof proceeds through the Euclidean algorithm. Yesterday at lunch I was surprised to learn (thanks to Ole Warnaar) of a different proof bypassing the Euclidean algorithm which I reproduce below. Its primary attraction is its cuteness, as it provides a weaker result than the usual proof (i.e. doesn’t prove that \mathbb{Z} is a Euclidean domain, or even a principal ideal domain).

Suppose that n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} where p_1,p_2,\ldots,p_k are distinct primes. Consider the finite cyclic group C_n. It has a composition series where the group C_{p_i} appears a_i times as a simple subquotient (and no other simple factors appear). Therefore by the Jordan-Holder theorem, the primes p_i together with their multiplicities a_i are unique. QED.

Leave a Comment

Filed under maths