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 (primes)

  1. Apr 23, 2010 #1
    1. The problem statement, all variables and given/known data

    I need to prove that a composite integer n>1 has a prime divisor p with p<=sqrt(n).

    2. Relevant equations

    3. The attempt at a solution

    Im not sure how to do this, any help getting started would be great thanks.
  2. jcsd
  3. Apr 23, 2010 #2
    Since you haven't showed us what you have done, i will simply give you an outline of the proof.

    You probably do realize that in order to show that a composite integer n>1, has a prime divisor p less than sqrt{n}, it suffices to show that n has a divisor, d, less than sqrt{n}.

    It is clear that, since n is a composite, then it must have a divisor, call it d', different from 1 and n itself. Hence 2<=d'<n.

    Now you will need to consider two cases:

    1. If d'<sqrt{n}, then what? and

    2. If d'>sqrt{n}, then what?

    After you have tried this, come back with more specific questions?

    Edit: This is actually a very neat result and it works both ways, namely: A positive integer n greater than 1 is composite iff n has a divisor d satisfying 2<=d<sqrt{n}.

    This tells us that whenever we want to check whether an integer n is composite or a prime, all we have to do is check whether it has a divisor up to sqrt{n}. Of course, if n is too large it is not that convenient, but for small n it works.

    Ex: let n=65. Then, we have a rough idea of what sqrt{65} equals, namely >8. So all we need to do is see whether 2, 3,..., 8 divide 65.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook