1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trouble understanding proof- infinitely many primes?

  1. Sep 9, 2012 #1
    I'm having trouble with this proof: Prove that there are infinitely many prime numbers, using proof by contradiction. My teacher gave it to us the first day of class, but I'm a little lost:

    Assume there are finitely many prime number,
    P1, P2, P3,.....,Pn.

    Let q=(P1*P2*P3*.....*Pn)+1

    Then, for all 1≤i≤n, Pi does not divide q, so therefore there must be at least Pn more prime, Pn+1.

    Here we reach a contradiction since we assumed there were only n primes. Therefore our assumption is in error and there are infinitely many primes. #

    I don't understand the portion in red. Can anyone please explain it in simple terms?

    Thanks.
     
  2. jcsd
  3. Sep 9, 2012 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What part do you specifically not understand? That pi doesn't divide q?
     
  4. Sep 9, 2012 #3
    It just means that based on how q is defined (all n primes multiplied, then one added) there is no prime that can divide q.

    This suggests that p is either a prime itself or is not composed of prime factors.

    The second case is impossible, and the first contradicts our claim of there being only n primes.
     
  5. Sep 9, 2012 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Instead of saying

    Then, for all 1≤i≤n, Pi does not divide q, so therefore there must be at least Pn more prime, Pn+1.
    you could expand this a little and say

    Then, for all 1 ≤ i ≤ n, q ≡ 1 (mod Pi). Thus, Pi does not divide q, so therefore there must be at least one more prime, Pn+1.
     
  6. Sep 9, 2012 #5
    I'm not sure how convincing this is, but maybe this will make it clear:



    Let
    [itex]k = x_{1}x_{2}....x_{n}[/itex] and [itex]x_{i} =/= 1[/itex]

    In other words, k equals a bunch of numbers multiplied, and we aren't letting any of them be one (because they have no effect on the value of k.)

    Now consider k + 1.

    [itex]k + 1 = x_{1}x_{2}....x_{n} + 1[/itex]

    Now lets assume that [itex]k + 1[/itex] is divisible by some [itex]x_{i}[/itex].

    Then, there exists some integer [itex]l[/itex] such that [itex]x_{i}l = k + 1[/itex]

    Then [itex]l = \frac{k}{x_{i}} + \frac{1}{x{i}}[/itex]

    But this doesn't make sense. [itex]\frac{k}{x_{i}}[/itex] is guaranteed to be an integer because we know that k is divisible by [itex]x_{i}[/itex], and [itex]\frac{1}{x_{i}}[/itex] is guaranteed to not be an integer, because it is the reciprocal of some non-one number.

    So, adding them together is guaranteed not to be an integer.

    Therefore, there isn't a single [itex]x_{i}[/itex] that divides [itex]k+1[/itex].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook