# How many ways are there to prove that there is no largest prime? [duplicate]

Is there any other proof by which I can show that there is no largest prime?

I saw an example where it is proved with contradiction.(Idea is basically that of Euclid's proof)

Imagine that the largest prime prime is $$13$$.So, total number of primes we know are-$$2,3,5,7,11,13$$.

Now,if I do $$(2\times3\times5\times7\times11\times13)+1=30031$$.So, we can see that $$30031$$ is not divisible by $$2,3,5,7,11,13$$ as they leave remainder $$1$$. Also,as it is formed by multiplying only primes it does not have any other composite factors.We also see that $$30031=59\times 509$$.Which are again two primes.Thus,$$13$$ is not the largest prime.

What are the other ways to prove that there is no largest prime?

Thanks for any proof!!

Note that all Fermat Numbers are coprime to each other.

Thus, if there are a finite number of prime numbers, this is a contradiction as there are infinite number of Fermat Numbers.

Thus, there are a infinite number of prime numbers.

And so there is no largest prime.

• What do you mean by all fermat numbers are co prime?Co prime to what? – tatan Feb 28 '16 at 5:55
• @tatan co-prime to each other. The first Fermat number is $2$, the second is $5$, and the third is $17$. These numbers are all coprime to each other. – S.C.B. Feb 28 '16 at 5:56
• Does it necessarily mean all Fermat numbers are prime numbers? – tatan Feb 28 '16 at 5:57
• @tatan No, it implies all Fermat numbers have distinct prime factors. Which is sufficient. – S.C.B. Feb 28 '16 at 5:58
• I don't find a reason to believe that there are an infinite number of Fermat Numbers unless there are an infinite number of primes. – TheRandomGuy Feb 28 '16 at 6:29

Well, the proof you have shown is not exactly the right way.

Proof: Assume there are a finite number of primes.

Let $s$ be the set of all primes possible. And let the primes be $p_1, p_2, p_3, \dots , p_n$.

Now by the Fundamental Theorem of Arithmetic, we know that every number is a prime or a unique product of primes.

Consider the number $p_1 p_2 p_3 \cdots p_n +1$. We know that it is not divisible by any of the numbers in the set $s$. Thus we get a number which is a prime or composed of primes not in the set $s$. That's a contradiction. Thus there are an infinite number of primes.

• There are two problems in this: 1. The number to be considered should be $p_1p_2p_3\cdots p_n+1$. 2. It does not necessarily follow that this number is a prime. It follows that either this number is a prime or there is its factors contain some other primes not included in $s$. Either way the conclusion holds. – GoodDeeds Feb 28 '16 at 6:23
• Yes. So the contradiction is you got a prime outside the set $s$. But $p_1p_2\cdots p_n+1$ is not necessarily that prime. It may also be the case that there was some other prime missed out in $s$, which leads to the same contradicton. – GoodDeeds Feb 28 '16 at 6:27
• @GoodDeeds Thanks. – TheRandomGuy Feb 28 '16 at 6:27

Let $p$ is the last prime. Then according to Bertrand's postulate the interval $(p,2p)$ consists a prime number. We get a contradiction.