Proof of there are an infinite number of primes by using the Fundamental Theorem of Arithmetic

Question

How can I show that there are an infinite number of primes by using the Fundamental Theorem of Arithmetic?

Answer 1

The standard way is by assuming that there are only a finite number of primes and deducing that if all terms of the form $\prod_{p \in P} p^{a(p)}$ are counted, there are not enough of them.

I don't remember the details, but it might go something like this:

The number of integers of the form $\prod_{p \in P} p^{a(p)}$ which are less that $x$ are of the form $\prod_{p \in P} p^{a(p)} \le x$ or $\sum_{p \in P} a(p)\ln p \le \ln x$.

We certainly have $a(p) \le \ln x/\ln p$.

The total number of possibilities is certainly less than, where $N$ is the number of primes, $\prod_{p \in P}(\ln x)/(\ln p) =(\ln x)^{N}\prod_{p \in P}1/(\ln p) $.

However, for every finite $N$, $(\ln x)^{N}$ will be less than $x$ for large enough $x$.

So $N$ must be infinite.

I just did this off the top of my head, so I'm not completely sure that it is correct, but it seems OK to me.

Anyway, there it is.

Answer 2

You start by assuming the opposite. Let's say there are a finite amount of prime numbers, in fact, let's write them in a list.

$P_1$, $P_2$, $P_3$, ... $P_n$

Note, this is a complete list.

Now let's form a new number $a$, by multiplying all of our prime numbers and adding $1$. According to the Fundamental Theorem of Arithmetic, every integer greater than $1$ is either prime or a unique factorization of primes. So let's try both of these possibilities.

Possibility 1: $a$ is prime. However, we previously wrote all the primes on our complete list, so this is a contradiction.

Possibility 2: $a$ is composite. However, if it is, it needs to be a unique factorization of the primes on our list. But, it won't divide $P_1$ exactly, $P_2$, $P_3$, or any $P_n$ for that matter. So it is a violation of the Fundamental Theorem of Arithmetic, and therefore a contradiction.

Because we get a contradiction when we assume there are finitely many primes, it must be the opposite, or there must be infinitely many primes.

Q.E.D