# Homework Help: Proof Involving Primes

1. Mar 19, 2012

### FreshUC

1. The problem statement, all variables and given/known data

Prove the following Theorem.
Let n ε Z. If n ≥ 2 and n is composite, then there exists a prime p such that p divides n and p ≤ √n.

After proving this Theorem show that if 757 is not a prime, then it has a prime divisor p ≤ 23.

3. The attempt at a solution
I really am confused on how to attack this proof. A little bit of insight on how I could start it would be appreciated. So far I've tried making n = xy becuase n is composite and have played around rearranging the different expressions but nothing seems to workout.

2. Mar 19, 2012

### tiny-tim

Welcome to PF!

Hi FreshUC! Welcome to PF!
Assume the opposite

that all such p are > √n

3. Mar 19, 2012

### FreshUC

Re: Welcome to PF!

Thanks for the hint!
Would I be correct then to assume the contrapositive of the statement then prove it to be true? my new assumption would be "If p does not divide n or p > √n Then n < 2 or n is prime."
Or is using the De Morgan's law here unnecessary?

4. Mar 19, 2012

### tiny-tim

uhh?

Start "suppose n ≥ 2 and n is composite, and all the prime divisors of n are > √2",

5. Mar 19, 2012

### FreshUC

so if n = 2 then p^2 > 2. But there is no prime number that can be squared and divide 2. So there is a contradiction? I dunno... maybe it's bed time for me haha

6. Mar 20, 2012

### FreshUC

Here is my solution not sure if it's quite right though.

To prove the theorem..

Assume n ≥ 2 where n is composite and all prime divisors of n are >√n.

Let n = 2
Since the only prime divisors of 2 is 1 or 2, then..
p = 1, or
p = 2

but If p = 1 then 1 > √2, Which is FALSE. This contradicts the assumption And so the Theorem is proven to be true.

For the second part of the question...

Assume the opposite, such that If 757 has a prime divisor greater than 23 then 757 is prime.

757 has a prime divisor of 757. And 757 > 23.

So by use of contrapositive it is then proven that 757 has a prime divisor p ≤ 23.

7. Mar 20, 2012

### tiny-tim

ok, you've proved it for n = 2

what about for n > 2 ??
what do you mean by "by use of contrapositive"?

and you haven't used the √ at all

8. Mar 20, 2012

### FreshUC

I see what you mean. Back to the drawing board with me. This is not going to well :yuck: