The Fundamental Theorem of Arithmetic

We shall prove in this section the following result.

Theorem 1.5.7 (Fundamental Theorem of Arithmetic)   If $ n>1$ is an integer then

$\displaystyle n=p_1^{e_1}p_2^{e_2}...p_m^{e_m}, $

where $ p_1<p_2...<p_m$ are primes and $ e_1>0$, $ e_2>0$, ..., $ e_m>0$ are integers. Furthermore, this representation of $ n$ is unique.

Before proving this result, we require a preliminary fact about primes.

Proposition 1.5.8 (Euclid's First Theorem)   An integer $ p>1$ is prime if and only if it satisfies the following property: for all integers $ a,b$, $ p\vert ab$ implies $ p\vert a$ or $ p\vert b$.

proof of Euclid's First Theorem: (only if) We may assume that $ a,b$ are non-zero. In this case, we have either $ gcd(a,p)=1$ or $ gcd(a,p)=p$ since $ p$ is a prime. In the latter case, $ p\vert a$ and we are done. By Proposition 1.2.16(3), $ p\vert gcd(a,p)b$, so if $ gcd(a,p)=1$ then $ p\vert b$.

(if) Assume for all integers $ a,b$, $ p\vert ab$ implies $ p\vert a$ or $ p\vert b$. If $ p$ was composite then $ p=ab$, for some $ a<p$ and $ b<p$. But $ p\vert p=ab$ would then imply $ p\vert a$ or $ p\vert b$, both of which are impossible. $ \Box$

In fact, rather than using Euclid's First Theorem directly in the proof of the Fundamental Theorem of Arithmetic, we use the following consequence of it.

Corollary 1.5.9 (of Euclid's First Theorem)   Let $ p$ be a prime. For any integers $ a_1,a_2,...,a_k$, $ p\vert a_1...a_k$ implies $ p\vert a_1$ or $ p\vert a_2$ or ... or $ p\vert a_k$.

We also need the following basic result.

Lemma 1.5.10   If $ m>1$ is an integer then the smallest $ d > 1$ which divides $ m$ must be a prime number.

proof of lemma: Let $ d > 1$ be the smallest positive divisor of $ m$. Suppose $ d$ has a factor $ b$ with $ 1<b\leq d$ and $ d=bc$. But $ b\vert d$ and $ d\vert m$ implies $ b\vert m$. Since $ d$ is the smallest factor of $ m$ which is greater than $ 1$, we must have $ b=d$, so $ d$ is prime. $ \Box$

proof of Fundamental Theorem of Arithmetic: First, we show that $ n$ is a product of primes.

If $ n$ is a prime then we are done, so we may assume $ n$ is not a prime.

Let $ n_0=n$ and let $ i=0$.

step 1: Let $ d_i>1$ denote the smallest divisor of $ n_i$. (By the above lemma, $ d_i$ is a prime.) Let $ n_{i+1}=n_i/d_i$. (Note: $ n_{i+1}<n_i$.)

step 2: If $ n_{i+1}$ is prime then stop. If $ n_{i+1}$ is not a prime then replace $ i$ by $ i+1$ and go to step 1.

Since $ n_0>n_1>...$, this process must eventually terminate. Say $ n_k$ is a prime. Then

$\displaystyle n=n_0=n_kd_{k-1}...d_0, $

so $ n$ is a product of primes.

By arranging the primes in increasing order and grouping identical primes in the product together, we may write $ n$ as in the statement of the theorem.

Now we prove uniqueness. Suppose

$\displaystyle n=p_1^{e_1}p_2^{e_2}...p_m^{e_m} =p_1^{f_1}p_2^{f_2}...p_m^{f_m}, $

where the $ p_i$'s are distinct primes but not necessarily in any particular order and the $ e_1,e_2,...,e_m,f_1,f_2,...,f_\ell$ are non-negative integers. (By allowing the exponents to be 0, we can insert ``dummy prime factors'' so that it looks as though both sides run over the same set of primes.)

We may suppose that $ e_1>0$ (some exponent must be greater than 0 since $ n>1$). By the corollary to Euclid's First Theorem, we must have $ p_1\vert p_1^{f_1}$ or $ p_1\vert p_2^{f_2}$ or ... $ p_1\vert p_m^{f_m}$. Since the $ p_i$'s are distinct, the only possibility is if $ p_1\vert p_1^{f_1}$, so in particular $ f_1>0$. If $ f_1>e_1$ then $ p_2^{e_2}...p_m^{e_m} =p_1^{f_1-e_1}p_2^{f_2}...p_m^{f_m}, $ and the corollary to Euclid's First Theorem implies $ p_1\vert p_2^{e_2}$ or ... $ p_1\vert p_m^{e_m}$. This is impossible since the $ p_i$'s are distinct. Similarly, $ e_1>f_1$ leads to a contradiction. This leaves the only possibility $ e_1=f_2$, so

$\displaystyle p_2^{e_2}...p_m^{e_m} =p_2^{f_2}...p_m^{f_m}. $

Proceeding inductively, we find $ e_2=f_2$, ..., $ e_m=f_m$. This proves uniqueness and the theorem. $ \Box$

Many important results in number theory are proved using prime factorization. The following theorem is an immediate consequence of the Fundamental Theorem of Arithemetic. The proof is left as an exercise.

Theorem 1.5.11   Let $ a=p_1^{e_1}\,p_2^{e_2}\,\cdots \,p_k^{e_k}$ and $ b=p_1^{f_1}\,p_2^{f_2}\,\cdots\,p_k^{f_k}$ be any positive integers with the given prime factorizations ($ e_i \geq 0,\,\,f_i \geq 0$, for all $ i$, $ 1 \leq i \leq k$). Then the following is true:


David Joyner 2007-09-03