# Homework Help: Another Prime number Proof

1. Jan 23, 2010

### scottstapp

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
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. Jan 23, 2010

### Dick

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
3. Jan 23, 2010

### scottstapp

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.

4. Jan 23, 2010

### Dick

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?

5. Jan 23, 2010

### scottstapp

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).

6. Jan 23, 2010

### Dick

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?

7. Jan 23, 2010

### scottstapp

By being integers greater than 1 and not in S, this says that a and b are integers that are divisible by a prime.

8. Jan 23, 2010

### Dick

Yes. Ok, so if b and c are divisible by primes what about a?

9. Jan 23, 2010

### scottstapp

Because bc divides a and a prime divides bc, then a prime divides a. Therefore a contradiction is reached.

10. Jan 23, 2010

### Dick

Exactly. So S must be empty.

11. Jan 23, 2010

### scottstapp

Thanks so much Dick. I figured I would attach my formal proof just in case of any errors.

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.

12. Jan 23, 2010

### Dick

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.