Does Every Integer Greater Than 1 Have a Prime Divisor? A Proof by Contradiction

[scottstapp]

Homework Statement

Let a be an integer greater than 1. Then there exists a prime that divides a.

Homework Equations

A prime is an integer that is greater than 1 but not composite

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

 

[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?

 

[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=a²/cb, so cba=a² but this is obvious. I think I am misinterpreting what you are getting at.

 

[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?

 

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

 

[Dick]

Doesn't this mean that one of them must be 1?

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?

 

[scottstapp]

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?

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

 

[Dick]

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

 

[scottstapp]

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

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

 

[Dick]

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

Exactly. So S must be empty.

 

[scottstapp]

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.

 

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