Infineti number of prime numbers proof

  • Thread starter lonerider
  • Start date
  • #1
12
0
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?
 

Answers and Replies

  • #2
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
Suppose some integer [itex]n>1[/itex] divides some larger integer [itex]m[/itex]. Can [itex]n[/itex] also divide [itex]m+1[/itex]?
 
  • #3
370
0
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:
  • #4
12
0
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
370
0
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:
  • #6
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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 [itex]p[/itex]. In other words, all integers [itex]n>p[/itex], including [itex]n=p!+1[/itex] must be divisible by some integer [itex]m>1[/itex]. What divides [itex]p!+1[/itex]?
 
  • #7
12
0
no number and therefore it is a prime number :)
 
  • #8
370
0
no number and therefore it is a prime number :)
Be careful! It's not necessarily prime. Why?
 
  • #9
12
0
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
370
0
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
12
0
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
StatusX
Homework Helper
2,564
1
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
370
0
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
703
13
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.

Derive a contradiction.
 

Related Threads on Infineti number of prime numbers proof

Replies
3
Views
2K
Replies
2
Views
1K
Replies
10
Views
18K
  • Last Post
Replies
2
Views
590
Replies
3
Views
1K
  • Last Post
Replies
15
Views
7K
  • Last Post
Replies
1
Views
671
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
6
Views
2K
Top