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


closed as off-topic by Shailesh, Morgan Rodgers, астон вілла олоф мэллбэрг, S.C.B., R_D Jan 29 '17 at 5:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shailesh, Morgan Rodgers, астон вілла олоф мэллбэрг, S.C.B., R_D
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ There were two answers. Why vote to close? Once again "This question is missing context or other details". What is needed? $\endgroup$ – marty cohen Jan 29 '17 at 5:29

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.


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.


  • 1
    $\begingroup$ I don't think this is what OP wanted. $\endgroup$ – D_S Jan 29 '17 at 6:15
  • $\begingroup$ @D_S Why not ? Euclid's proof exactly uses the mentioned theorem. I upvoted this answer and I am surprised that it has received no upvotes, but the much more complicated approach received $2$. $\endgroup$ – Peter Jan 29 '17 at 14:55
  • $\begingroup$ We do not even need the unique factorization theorem, if we modify the proof a bit : Step 1 : Every integer $N>1$ is divisble by at least one prime. Proof : The set of integers $t>1$ with $t|N$ is not empty because of $N|N$. Let $p$ be the smallest element of this set. Then, $p$ must be a prime, otherwise there would be an integer $a$ with $1<a<p$ and $a|p$ implying $a|N$. But this contradicts the choice of $p$. Step 2 : Assume , $p_1,\cdots , p_k$ are all the primes. Then the number $p_1\cdot \ \cdots\ \cdot p_k+1$ is divisble by no prime contradicting the claim we get in Step $1$ $\endgroup$ – Peter Jan 29 '17 at 15:04
  • $\begingroup$ I found this version of Euclids proof in a german algebra-book and it is my favorite way to show that there are infinite many primes. $\endgroup$ – Peter Jan 29 '17 at 15:08
  • $\begingroup$ The fundamental theorem of arithmetic doesn't feel essential in this proof. I think we could transplant this proof to a ring that is not a unique factorization domain to show that it has infinitely many irreducible numbers. $\endgroup$ – Robert Soupe Jan 29 '17 at 17:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.