# The Fundamental Theorem of Arithmetic

This post discusses and proves the fundamental theorem of arithmetic.

Finding the prime factors of a large integer is no easy feat. For example, the ninth Fermat number $F_9=2^{2^9}+1$ has 155 digits and has the following three prime factors:

$a=\text{2,424,833}$

$b=\text{7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657}$

\displaystyle \begin{aligned} c=&\text{ 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519} \\&\text{ 023,905,821,316,144,415,759,504,705,008,092,818,711,693,940,737} \end{aligned}

These prime factors have 9 digits, 49 digits and 99 digits, respectively. They were published in 1993 after lengthy calculations involving approximately 700 workstations and a supercomputer using a number field sieve algorithm (see [1]). If the project were to be done today, it could certainly be done much faster and more efficiently with the current state of the art in supercomputing. However, the project will still be no trivial feat.

The following 617-digit integer is a product of two prime numbers and has yet to be factored by anyone (or any computer or any sets of computers). According RSA Laboratories, barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come. For more background about this large number, see see RSA challenge number and RSA factoring challenge.

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

Though the implementation of prime factorization may be difficult or even impossible for large numbers, the fundamental theorem of arithmetic guarantees that any positive integer can be expressed uniquely as a product of prime numbers. The fundamental theorem of arithmetic is an essential theorem in number theory. In this post, we present of proof of this fundamental theorem.

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

The theorem has two parts – the existence and the uniqueness of the prime factorization. The existence part is relatively easy. We first prove the existence part. We use Euclid’s lemma to prove the uniqueness part.

Lemma 1

Any integer $n>1$ has a prime divisor.

Proof

Let $n$ be an integer with $n>1$. If $n$ is prime, then it has a prime divisor, namely $n$. So assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$.

Now consider the set $D$ of all positive integer divisors of $n$. The set $D$ is nonempty since $h$ and $k$ belong to this set. The set $D$ is also a finite set since an integer can only have finitely many integer divisors. Every finite set of real numbers has a smallest element. Let $p$ be the least element of $D$.

The $p$ must be a prime number. If not, $p$ would have a positive divisor $q$ that is smaller than $p$. Then $q$ is also a positive divisor of $n$, contradicting that $p$ is the least element of $D$. $\blacksquare$

Lemma 2

Any integer $n>1$ is a product of prime numbers.

Proof

We prove by induction. The lemma is certainly true for $n=2$. Suppose the lemma is true for all positive integers $k$ where $k.

If $n$ is prime, then we are done. Assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$. By induction hypothesis, both $h$ and $k$ are product of prime numbers. We can conclude that $n$ is also a product of prime numbers. $\blacksquare$

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof of Euclid’s Lemma is found in this post. As a corollary of Euclid’s Lemma, we have the following lemma.

Lemma 3

If $p$ is a prime number and $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$, then $p \ \lvert \ a_i$ for some $i$.

Proof

We prove by induction. The case for $n=2$ is the Euclid’s Lemma. Assume that the lemma is true for $n$ where $n \ge 2$. Suppose that $p \ \lvert (a_1 \cdot a_2 \cdots a_n \cdot a_{n+1})$. By Euclid’s lemma, we have $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$ or $p \ \lvert \ a_{n+1}$. In the first case, the induction hypothesis tells us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n$. In the second case $p \ \lvert \ a_{n+1}$. The two cases together tell us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n+1$.

Since the validity of the lemma for $n$ implies the validity of the lemma for $n+1$ and since the lemma is true for $n=2$, we now know that the lemma is true for all integers $n>1$. This establishes the lemma. $\blacksquare$

Fundamental Theorem of Arithmetic

Any interger $n>1$ can be expressed uniquely as a product of prime numbers.

Proof

Let $n$ be an integer with $n>1$. The existence of the prime factors of $n$ is established by Lemma 2. We now show there is only one prime factorization for $n$. We would like to point out that order of the prime factors is not important. For example, we consider $2 \times 2 \times 3 \times 11$ and $11 \times 3 \times 2 \times 2$ as the same factorization for the integer $132$.

Suppose that $n=p_1 \cdot p_2 \cdots p_h$ and $n=q_1 \cdot q_2 \cdots q_k$ are prime factorizations of the integer $n$. We show that each $p_i$ is identical to some $q_j$ and each $q_s$ is identical to some $p_t$. This implies that the prime numbers $p_1,p_2,\cdots,p_h$ are simply a rearrangement of $q_1,q_2,\cdots,q_k$ such that the only difference for the two factorizations is in the order of the factors.

Note that $p_1 \cdot (p_2 \cdots p_h)=q_1 \cdot q_2 \cdots q_k$. Thus $p_1$ divides $q_1 \cdot q_2 \cdots q_k$, or we write $p_1 \ \lvert \ q_1 \cdot q_2 \cdots q_k$. By Lemma 3, $p_1 \ \lvert \ q_j$ for some $j$. Since they are prime, $p_1=q_j$. Then cancel out $p_1$ on both side of the equation, we have

$p_2 \cdot (p_3 \cdots p_h)=q_1 \cdot q_2 \cdots q_{j-1} \cdot q_{j+1} \cdots q_k$

Note that $p_2$ divides the right-hand side of the above equation. By Lemma 3, $p_2 \ \lvert \ q_w$ for some $w$. Continue in this same manner, we see that each $p$ is identical to some $q$. Furthermore, $h \le k$. Otherwise, there would be some $p_i$ left after we cancel out all the $q_j$, leading to the situation that the product of several prime numbers is equal to one.

By interchanging $p$ with $q$, the same argument will also show that each $q$ is identical to some $p$. Furthermore, $k \le h$. Thus we have $h=k$ and that the two factorizations are really just rearrangement of each other. $\blacksquare$

Comment

From the fundamental theorem of arithmetic, it follows that any positive integer greater than one can be expressed uniquely in the following way:

$p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_m^{e_m}$

where $m$ is a positive integer and each $e_i \ge 1$. Such representation of an integer is called a prime-power decomposition. For example, $7056=2^4 \cdot 3^2 \cdot 7^2$.

___________________________________________________________________________________________________________________

Reference

1. Lenstra, A. K., Lenstra, H. W., Manasse, M. S., Pollard, J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$