Results 1 to 2 of 2

Math Help - Prime number problem

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    6

    Prime number problem

    Let n be a positive integer with n not equal to 1. Suppose that n is not a prime number. Show that there is a prime number p such that p divides n and p is less than or equal to the square root of n.

    I have no idea where to start with this. Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by Revilo View Post
    Let n be a positive integer with n not equal to 1. Suppose that n is not a prime number. Show that there is a prime number p such that p divides n and p is less than or equal to the square root of n.

    I have no idea where to start with this. Any help would be appreciated.
    Okay, n is an integer and is not prime, this means it has a positive divisor other than itself, and that divisor is prime (based on the Fundamental Theorem of Arithmetic which says: Every positive integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size.)

    So we know that some prime number divides n, we'll name that prime number p_1, and say that the quotient is some integer a (it must be an integer because if it wasn't, then p would not divide n)

    right, so p_1 *a = n (which coincidentally spells pan, but that's not part of the proof)

    Now, either p_1 or a is < \sqrt{n} because if neither was, then both would be greater than the \sqrt{n} And if they were both greater than the \sqrt{n} we could say that p_1 * a > n However, \sqrt{n} * \sqrt{n} = n and a*p_1 = n so this is a contradiction.

    This means that either p_1 or a is not greater than \sqrt{n} therefore either p_1 or a must be less than \sqrt{n}.

    If p_1 is less than \sqrt{n} then there is a prime number which divides n and is less than the \sqrt{n}. If p_1 is greater than \sqrt{n}, then a must be less than \sqrt{n}. And by the Fundamental Theorem of Arithmetic, a is either prime, or the product of two or more primes, so either a or one of its factors is prime. So there is a prime number less than \sqrt{n} which divides n.



    It's also worth pointing out that there is a theorem which says if a divides b, and b divides c, then a divides c. This is for if your instructor wants you to show that if a is less than the \sqrt{n}, but a is not prime, then one of a's prime factors will divide n.
    Last edited by angel.white; November 6th 2007 at 02:35 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime number problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 8th 2010, 10:12 PM
  2. Prime number problem
    Posted in the Algebra Forum
    Replies: 6
    Last Post: June 12th 2010, 12:49 PM
  3. [SOLVED] prime number problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 27th 2009, 04:11 PM
  4. A prime number problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 28th 2009, 03:13 PM
  5. Prime number problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 12th 2009, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum