Skip to main content

Section 3.1 The Fundamental Theorem of Arithmetic

Let \(p\) be a prime and \(p\vert ab,\) and suppose that \(p \nmid a.\) Since \(p\) is prime and \(p \nmid a\) we have that \(\gcd(p,a)=1,\) so that by Euclid's Lemma \(p\vert b.\)

We induct on the number of factors. Let \(p\) be a prime. If \(n=1\) this is clear. When \(n=2,\) the result is the preceding theorem. Suppose that \(n\gt 2\) and that whenever \(p\) divides a product of less than \(n\) factors, then \(p\) divides at least one of the factors.

Now let \(p\vert a_1 a_2...a_n.\) By the previous theorem, we have that

\begin{equation*} p\vert a_1 a_2...a_{n-1} \hspace{5mm} \mathrm{or} \hspace{5mm} p\vert a_n. \end{equation*}

If \(p\vert a_n\) we are done. If \(p\vert a_1 a_2...a_{n-1},\) then by hypothesis, \(p\vert a_k\) for some \(k\) where \(1\leq k\leq n-1.\) In any case, \(p\) divides at least one of \(a_1,a_2,...a_n.\)

Apply the preceding corollary and the fact that if \(p,q\) are primes and \(p\vert q,\) then \(p=q.\)

By induction on \(n.\) The case \(n=2\) is clear. Suppose that any integer \(k\) with \(2\leq k \lt n\) can be written uniquely as a product of primes.

If \(n\) is a prime, then \(n = p\) is the product of primes.

If \(n\) is not a prime, then \(n\) has a proper divisor, say \(d_1,\) with

\begin{equation*} 1\lt d_1\lt n d_1\vert n. \end{equation*}

Write \(n = d_1d_2.\) It is clear here that \(1\lt d_2\lt n.\) By the induction hypothesis

\begin{equation*} d_1 = p_1p_2...p_r \hspace{5mm} d_2 = q_1q_2...q_s \end{equation*}

can be written uniquely as a product of primes. Thus

\begin{equation*} n = d_1d_2 = p_1p_2...p_rq_1q_2...q_s, \end{equation*}

and \(n\) is the product of primes.

For uniqueness, we again use induction. For \(n = 2\) this is clear. Now suppose that for any integer \(k\) with \(2\leq k \lt n\) has a unique representation as a product of primes.

Again the case \(n = p\) is clear. If \(n\) is not a prime, then suppose that \(p_i\)'s and \(q_i\)'s are prime, and

\begin{equation*} n = p_1p_2...p_r = q_1q_2...q_s. \end{equation*}

Note that \(p_1\vert q_1q_2...q_s\) so that by the above Corollary \(p_1 = q_j\) for some \(j.\) Without loss of generality let \(j = 1.\) Now

\begin{equation*} p_2p_3...p_r = q_2q_3...q_s =\frac{n}{p_1}\lt n, \end{equation*}

so that by the induction hypothesis, \(\frac{n}{p_1}\) has a unique factorization. Thus \(r = s,\) and \(p_i = q_i\) for all \(i\leq r.\)

Thus by induction every integer \(n\gt 1\) can be expressed uniquely as a product of primes.

Toward a contradiction, suppose that there are only finitely many primes, say \(p_1, p_2,..., p_n.\) Consider the number \(n,\) where

\begin{equation*} m = p_1p_2...p_n + 1. \end{equation*}

From a previous lecture we know that

\begin{equation*} \gcd(p_1p_2...p_n, m) = 1. \end{equation*}

Also \(m\gt 1,\) since \(2\) is a prime, so that \(m\) is prime or a product of primes, and \(m\gt p_i\) for any \(i\leq n.\) If \(n\) is prime, we are done. If \(m\) is not prime, then it has a prime divisor which is not one of \(p_1, p_2,..., p_n.\) In any case the list \(p_1, p_2,..., p_n\) is incomplete, and so there are infinitely many primes.

Definition 3.1.7.

We define the integer part of \(x,\) written \(\lfloor x\rfloor,\) as the greatest integer less than or equal to \(x.\) This is sometimes called the floor function.

In this proof, we consider the sum

\begin{equation*} \sum_{p_1^{k_1}...p_n^{k_n}\leq x} 1, \end{equation*}

where the sum is taken over all possible choices of \(k_1, k_2,..., k_n\) that satisfy the inequality \(p_1^{k_1}...p_n^{k_n}\leq x.\) By induction one has that

\begin{equation*} \sum_{p_1^{k_1}...p_n^{k_n}\leq x} 1 \leq \left(\sum_{p_1^{k_1}\leq x} 1\right)\left(\sum_{p_2^{k_2}\leq x} 1\right)...\left(\sum_{p_n^{k_n}\leq x} 1\right) = \prod_{i=1}^{n} \left(\sum_{p_i^{k_i}\leq x} 1\right). \end{equation*}

Now \(p_1 = 2,\) and we have

\begin{equation*} \sum_{p_1^{k_1}\leq x} 1 = \sum_{2^{k_1}\leq x} 1 = \left\lfloor \frac{\log(x)}{\log(2)}\right\rfloor +1\leq \frac{\log(x)}{\log(2)}+\frac{1}{\log(2)}=\frac{1}{\log(2)}(\log(x)+1). \end{equation*}

For \(i \geq 2,\) we have that \(\log(p_i)\geq \log(3)\geq 1,\) so that

\begin{equation*} \sum_{p_i^{k_i}\leq x} 1 = \left\lfloor \frac{\log(x)}{\log(p_i)}\right\rfloor +1\leq \frac{\log(x)}{\log(p_i)}+1\leq \log(x)+1. \end{equation*}

Putting this together gives (for \(x\geq e\))

\begin{equation*} \sum_{p_1^{k_1}...p_n^{k_n}\leq x} 1 \leq \prod_{i=1}^{n}\left(\sum_{p_i^{k_i}\leq x} 1\right)\leq \frac{1}{\log(2)}(\log(x)+1)^n\leq \frac{2}{\log(2)}\log^n(x)=O(\log^n(x)). \end{equation*}

If there were finitely many primes, say \(n,\) then since there are about \(x\) numbers less than \(x,\) we would have to have

\begin{equation*} \sum_{p_1^{k_1}...p_n^{k_n}\leq x} 1 =\lfloor x\rfloor \geq x-1. \end{equation*}

But \(x\neq O(\log^n(x))\) for any fixed \(n.\) Hence there are infinitely many primes.

We now make more explicit a lemma used above.

Note that the sums in (3.1.1) are just counting the number of elements of a certain form. The sum on the left-hand side of (3.1.1) is equal to the size of the set

\begin{equation*} A := \{m \leq x: m = a_1^{k_1}...a_n^{k_n} \hspace{2mm} \mathrm{for} \hspace{2mm} \mathrm{some} \hspace{2mm} k_1,...,k_n\geq 0\}, \end{equation*}

and the product of sums on the right-hand side of (3.1.1) is equal to the size

\begin{equation*} B := \{m: m = a_1^{k_1}...a_n^{k_n} \hspace{2mm} \mathrm{for} \hspace{2mm} \mathrm{some} \hspace{2mm} k_1,...,k_n\geq 0 \hspace{2mm} \mathrm{where} \hspace{2mm} \mathrm{both} \hspace{2mm} a_1^{k_1}...a_{n-1}^{k_{n-1}}\leq x \hspace{2mm} \mathrm{and} \hspace{2mm} a_n^{k_n}\leq x\}. \end{equation*}

Thus to prove the lemma, we need to show that the number of elements in \(A\) is at most the number of elements in \(B.\) Since both \(A\) and \(B\) are finite sets, it is enough to show that \(A\subseteq B.\)

To this end, let \(m\in A.\) Then there exist \(k_1,..., k_n\geq 0\) for which

\begin{equation*} m = a_1^{k_1}...a_n^{k_n}\leq x. \end{equation*}

Note that also \(m = a_1^{k_1}...a_{n-1}^{k_{n-1}}\cdot a_n^{k_n},\) and that since \(m\leq x,\) we have both

\begin{equation*} m = a_{n-1}^{k_{n-1}}\leq \frac{x}{a_n^{k_n}}\leq x \end{equation*}

and

\begin{equation*} a_n^{k_n}\leq \frac{x}{a_1^{k_1}...a_{n-1}^{k_{n-1}}}\leq x. \end{equation*}

Thus \(m\in B,\) so that \(A\subseteq B\) and the lemma is proved.

Going on to Euler's proof, we need a small result relating infinite products to infinite sums.

Taking the logarithm of the product does not change the convergence properties. Hence the product converges if and only if the sum

\begin{equation*} \sum_{n=1}^{\infty} \log(1+a_n) \end{equation*}

converges. Recall that

\begin{equation*} \lim_{x\rightarrow 0}\frac{\log(1+x)}{x}=1. \end{equation*}

Since \(a_n\rightarrow 0\) as \(x\rightarrow\infty,\) applying the above limit, we have

\begin{equation*} \lim_{n\rightarrow \infty}\frac{\log(1+a_n)}{a_n}=1. \end{equation*}

We can now just apply the limit comparison test to give the result.

Note that by the fundamental theorem of arithmetic we have that

\begin{equation*} \sum_{n\leq x}\frac{1}{n}\leq \prod_{p\leq x}\left(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+...\right). \end{equation*}

This product converges if and only if the sum

\begin{equation*} \sum_{p\leq x}\left(\frac{1}{p}+\frac{1}{p^2}+...\right). \end{equation*}

Well we have, again using geometric series, that

\begin{align*} \sum_{p\leq x}\left(\frac{1}{p}+\frac{1}{p^2}+...\right) \amp = \sum_{p\leq x} \frac{1}{p}+\sum_{p\leq x}\left(\frac{1}{p^2}+...\right)\\ \amp = \sum_{p\leq x} \frac{1}{p}+\sum_{p\leq x}\frac{1}{p}\cdot\frac{1}{p-1}\\ \amp \leq \sum_{p\leq x} \frac{1}{p}+\sum_{n=1}^{\infty}\frac{1}{n^2}\\ \amp = \sum_{p\leq x} \frac{1}{p}+C \end{align*}

for some real number \(C\gt 0.\) Thus the product converges if and only if the sum

\begin{equation*} \sum_{p\leq x}\frac{1}{p} \end{equation*}

converges. Since the harmonic series diverges, we thus have that the sum of the reciprocals of the primes diverges. Since a sum of finitely many terms would be finite, there are infinitely many primes.