Proving the Existence of Prime Divisors for Composite Numbers

[FreshUC]

Homework Statement

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.

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.

 

[tiny-tim]

Welcome to PF!

Hi FreshUC! Welcome to PF!

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

Assume the opposite …

that all such p are > √n ​

 

[FreshUC]

Hi FreshUC! Welcome to PF! Assume the opposite …

that all such p are > √n ​

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?

 

[tiny-tim]

"If p does not divide n or p > √n Then n < 2 or n is prime."

uhh?

sorry, but that's almost unreadable! ​

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

and prove a contradiction!

 

[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

 

[FreshUC]

uhh?

sorry, but that's almost unreadable! ​

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

and prove a contradiction!

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.

 

[tiny-tim]

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.

ok, you've proved it for n = 2

what about for n > 2 ?? ​

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.

what do you mean by "by use of contrapositive"?

and you haven't used the √ at all

 

[FreshUC]

ok, you've proved it for n = 2
I really need to stop doing that

what about for n > 2 ?? ​

what do you mean by "by use of contrapositive"?
Proving notq →notp instead of p→q because they are logically equivalent.
and you haven't used the √ at all

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