# Infineti number of prime numbers proof

1. Mar 4, 2007

### lonerider

I have to prove that there excist an infinite number of prime numbers

In that proof I apply that:

n=p!+1 (where p is a prime number)

this number (n) is not divisible with any prime number less than or equal to p. Why is that? Is there anyone who could please explain this to me or maybe make it probale to me?

2. Mar 4, 2007

### D H

Staff Emeritus
Suppose some integer $n>1$ divides some larger integer $m$. Can $n$ also divide $m+1$?

3. Mar 4, 2007

### ZioX

The important lemma in infintely many primes is that every number is a product of primes. Suppose there are only finitely many primes. This guarantees the existence of a largest prime p. Consider the number n=p!+1. Now this number must be a product of primes (by the lemma). What can you say about all the other primes induced by the hypothesis? Remember p was the largest prime. Now what does this tell you about n? A very common mistake with students is that they will say n is prime. This is not necessarily true. Why?

Last edited: Mar 4, 2007
4. Mar 4, 2007

### lonerider

ZioX I must say that I do not really get it because I cannot really see what it has to do with the prime numbers less than p, and how they should be divisble with n.

5. Mar 4, 2007

### ZioX

What can you say if a number d divides b+c? What can you say if a number d does not divide b+c? Suppose d divides b but does not divide c, does d divide b+c?

Edit: Okay, Oops. I misread you.

Every number must be a product of primes. That is, every number must be divisible by some prime.

In our proof, we supposed that there were finitely many of them. This means that there exists a maximal prime p. So now, consider n=p!+1. Can our primes divide n? Why or why not?

Last edited: Mar 4, 2007
6. Mar 4, 2007

### D H

Staff Emeritus
The proof is by contradiction. If there aren't an infinite number of primes, there are only a finite number of them. Assuming this is the case (a finite number of primes), there must exist some largest prime $p$. In other words, all integers $n>p$, including $n=p!+1$ must be divisible by some integer $m>1$. What divides $p!+1$?

7. Mar 4, 2007

### lonerider

no number and therefore it is a prime number :)

8. Mar 4, 2007

### ZioX

Be careful! It's not necessarily prime. Why?

9. Mar 4, 2007

### lonerider

So well the thing is that you have this number n=p!+1

As p is the biggest prime number n should be divisble with some number. We do not know any number which is divisble with p! and 1 but 1. And we have to find a number larger than that - but we cannot. As that the definition of a prime number n must be a prime number and as it is bigger than p the statement has been proven false which proves that there is no biggest prime number which means there is an infinite number of prime numbers.

Am I on the right track?

10. Mar 4, 2007

### ZioX

Close but no cigar. Every number must be divisible by some prime. (This has nothing to do with the maximality of p). Now, no number between 1 and p divides p!+1. You should prove this, THIS has something to do with the maximality of p. Therefore, there does not exist a prime number that divides p!+1. Contradiction. Therefore there must be infinitely many primes.

11. Mar 4, 2007

### lonerider

In the proof the do not prove that statement they just say because of that we can conclude bla bla should you prove that part in order to make a proper proof?

12. Mar 4, 2007

### StatusX

It's slightly simpler to assume p1, p2,..., pn are all the primes, and then look at p1p2...pn+1. Very slightly. Almost too slightly for me to bother mentioning. But not quite.

13. Mar 4, 2007

### ZioX

I'm sorry, but you're going to have to be more specific. I'm not really sure what you're talking about.

Do you mean that any number between 1 and p does not divide p!+1? Of course you don't have to prove it, but it's an easy proof. It builds 'mathematical maturity'. Besides, there's nothing I hate more than one of those damn combinatorial paragraph proofs.

14. Mar 4, 2007

### Edgardo

Hello lonerider,

try to derive a contradiction by considering the following:

Assume that p is the largest prime number.
Either
(i) n is prime or
(ii) n is not prime.