1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Proof Involving Primes

  1. Mar 19, 2012 #1
    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. jcsd
  3. Mar 19, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi FreshUC! Welcome to PF! :smile:
    Assume the opposite

    that all such p are > √n :wink:
  4. Mar 19, 2012 #3
    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?
  5. Mar 19, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    uhh? :confused:

    sorry, but that's almost unreadable! :redface:

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

    and prove a contradiction! :smile:
  6. Mar 19, 2012 #5
    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
  7. Mar 20, 2012 #6
    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.
  8. Mar 20, 2012 #7


    User Avatar
    Science Advisor
    Homework Helper

    ok, you've proved it for n = 2

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

    and you haven't used the √ at all :redface:
  9. Mar 20, 2012 #8
    I see what you mean. Back to the drawing board with me. This is not going to well :yuck:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook