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

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook