Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infineti number of prime numbers proof

  1. Mar 4, 2007 #1
    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. jcsd
  3. Mar 4, 2007 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Suppose some integer [itex]n>1[/itex] divides some larger integer [itex]m[/itex]. Can [itex]n[/itex] also divide [itex]m+1[/itex]?
  4. Mar 4, 2007 #3
    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
  5. Mar 4, 2007 #4
    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.
  6. Mar 4, 2007 #5
    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
  7. Mar 4, 2007 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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]?
  8. Mar 4, 2007 #7
    no number and therefore it is a prime number :)
  9. Mar 4, 2007 #8
    Be careful! It's not necessarily prime. Why?
  10. Mar 4, 2007 #9
    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?
  11. Mar 4, 2007 #10
    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.
  12. Mar 4, 2007 #11
    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?
  13. Mar 4, 2007 #12


    User Avatar
    Homework Helper

    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.
  14. Mar 4, 2007 #13
    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.
  15. Mar 4, 2007 #14
    Hello lonerider,

    try to derive a contradiction by considering the following:

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

    Derive a contradiction.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook