Theorem.(Fundamental Theorem of Arithmetic)
Every integer greater than \(1\) can be written as a product of primes and the product is unique if prime factors are written in non-decreasing order.
In the unique prime factorization we can replace the product of the same prime by a prime power to get a unique prime-power factorization: Every integer \(n>1\) can be written as
\[n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k},\]
for some unique primes \(p_1< p_2<\cdots < p_k\) and unique positive integers \(a_1,a_2,\ldots,a_k.\)
Note that if \(1\) were prime, then we do not have the uniqueness in the prime factorization. For example, \(3=1\cdot 3=1\cdot 1\cdot 3.\)
Proof of FTA. (Existence) We prove the existence of prime factorization of \(n>1\) by induction. For \(n=2\), \(n\) is a prime which is a prime product with a single term. Suppose we have prime factorization for all integers \(n=2,3,\ldots,k\). Let \(n=k+1\). If \(n=k+1\) is a prime, then it is a prime product with a single term.
Otherwise \(n=k+1=ab\) for some integers \( a,b,\; 1< a,b < k+1\). By the induction hypothesis, \(a=p_1\cdot p_2\cdots p_r\) and \(a=q_1\cdot q_2\cdots q_s\) for some primes \(p_1,p_2,\ldots, p_r, q_1,q_2,\ldots, q_s\). Then \(n=k+1=ab=p_1\cdot p_2\cdots p_r\cdot q_1\cdot q_2\cdots q_s\). So by mathematical induction we have prime factorization for all integers \(n>1\).
◼
To prove the uniqueness of prime factorization, we need the following results.
Lemma.(Euclid's Lemma)
Let \(a\) and \(b\) be integers. If a prime \(p\vert ab\), then \(p\vert a\) or \(p\vert b\).
Proof.
If \(p\vert a\), we are done. Otherwise \(p\nmid a\) and consequently \(\gcd(a,p)=1\). By Bézout's Lemma, \(1=\gcd(a,p)=ax+py\) for some integers \(x\) and \(y\). Then \(b=abx+pby\). Since \(p\vert ab\) and \(p\vert pb\), \(p\vert abx+pby=b\).
◼
Applying Euclid's lemma inductively we get the following result.
Corollary. Let \(p\) be a prime and \(a_1,a_2,\ldots,a_n\) be integers.
If \(p\vert a_1\cdot a_2\cdots a_n\), then \(p\vert a_k\) for some \(k=1,2,\ldots,n\).
If \(p\vert a_1\cdot a_2\cdots a_n\) and \(a_1,a_2,\ldots,a_n\) are primes, then \(p=a_k\) for some \(k=1,2,\ldots,n\).
Proof of FTA. (Uniqueness) Suppose \(n=p_1\cdot p_2\cdots p_r\) and \(n=q_1\cdot q_2\cdots q_s\) for some primes \(p_1\leq p_2 \leq\cdots\leq p_r\), \(q_1\leq q_2\leq\cdots\leq q_s\). We show \(r=s\) and \(p_i=q_i\) for \(i=1,2,\ldots,r\).
Since \(p_1\vert q_1\cdot q_2\cdots q_s\), \(p_1=q_k\) for some \(k\) by the preceding corollary. Then \(p_1\geq q_1\). Similarly we can show that \(q_1\geq p_1\). Thus \(p_1=q_1\) and \(p_2\cdot p_3\cdots p_r=q_2\cdot q_3\cdots q_s\). Repeating this process, we get \(p_2=q_2\) and \(p_3\cdot p_4\cdots p_r=q_3\cdot q_4\cdots q_s\). Continuing this process we get \(p_r=q_r\) and \(1=q_{r+1}\cdots q_s\) if \(rs\). Since each \(p_i,q_j>1\), we cannot have \(1=q_{r+1}\cdots q_s\) and \(p_{s+1}\cdots p_r=1\). Thus \(r=s\) and \(p_i=q_i\) for \(i=1,2,\ldots,r\).
◼