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!

Another Prime number Proof

  1. Jan 23, 2010 #1
    1. The problem statement, all variables and given/known data
    Let a be an integer greater than 1. Then there exists a prime that divides a.


    2. Relevant equations
    A prime is an integer that is greater than 1 but not composite


    3. The attempt at a solution
    Via Contradiction
    S={x:x is an integer, x>1, x is not divisible by any prime }, assume S is nonempty.

    I believe this is the set I must use, but I am not sure how to start this proof.

    Thank you
     
  2. jcsd
  3. Jan 23, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Let a be the smallest integer greater than 1 that is not divisible by a prime. I.e. the smallest element of your set S. Since a isn't prime, a=b*c where b>1 and c>1. Now what? How do b and c compare with a in size?
     
    Last edited: Jan 23, 2010
  4. Jan 23, 2010 #3
    I'm not sure if I am understanding what you are getting at but this is what I am thinking:

    Because a=b*c, b=a/c, c=a/b, so a=a2/cb, so cba=a2 but this is obvious. I think I am misinterpreting what you are getting at.
     
  5. Jan 23, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm trying to get you to tell me that b and c are smaller than a. Therefore they AREN'T in your set S. What does that mean about b and c?
     
  6. Jan 23, 2010 #5
    Doesn't this mean that one of them must be 1? And therefore the other is a prime because it is only written as 1*c (or 1*b).
     
  7. Jan 23, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No. a isn't prime. So it's composite. So a=b*c where b and c are greater than 1. If they are not 1 and they are not in S, then what does the definition of S say about them?
     
  8. Jan 23, 2010 #7
    By being integers greater than 1 and not in S, this says that a and b are integers that are divisible by a prime.
     
  9. Jan 23, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. Ok, so if b and c are divisible by primes what about a?
     
  10. Jan 23, 2010 #9
    Because bc divides a and a prime divides bc, then a prime divides a. Therefore a contradiction is reached.
     
  11. Jan 23, 2010 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Exactly. So S must be empty.
     
  12. Jan 23, 2010 #11
    Thanks so much Dick. I figured I would attach my formal proof just in case of any errors.

    Proof by Contradiction:
    1. Let S={x:x is an integer, x>1, x is not divisible by any prime}, assume S is nonempty.
    2. Let a be the smallest integer greater than 1 that is not divisible by a prime, therefore it is the smallest integer in S.
    3. a is composite so there exist integers b and c such that a=bc where b>1 and c>1
    4. From (2) we know that a is the smallest integer in S therefore b and c are not in set S.
    5. From (3), because b and c are greater than 1 and not in S, they must be divisible by a prime.
    6. Therefore, bc|a, prime|bc, so prime|a and a contradiction is reached because S is empty.
     
  13. Jan 23, 2010 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You forgot to say that because a=b*c and b>1, and c>1 then b<a and c<a to justify your step 4. But other than that, it looks fine.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Another Prime number Proof
  1. Prime number proof (Replies: 2)

  2. Prime Number Proof (Replies: 6)

Loading...