Results 1 to 4 of 4

Math Help - Prove composite number has a prime divisor

  1. #1
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318

    Prove composite number has a prime divisor

    Prove that if integer n>=2 is composite, then n has a prime divisor which is <=(n)^1/2


    My first thought was to somehow use the fundamental theorem of arithmetic.
    I have n=p1p2...pr.
    I assumed each integer >=2 can be factored into primes.
    Then assuming k+1 is composite, we have k+1=ab where 2<=a,k+1 and 2<=b<k+1. But at this step I get stuck.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kathrynmath View Post
    Prove that if integer n>=2 is composite, then n has a prime divisor which is <=(n)^1/2


    My first thought was to somehow use the fundamental theorem of arithmetic.
    I have n=p1p2...pr.
    I assumed each integer >=2 can be factored into primes.
    Then assuming k+1 is composite, we have k+1=ab where 2<=a,k+1 and 2<=b<k+1. But at this step I get stuck.
    Assume otherwise, so that all prime divisors of  n are greater than  \sqrt{n}

    Then  n=p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k} > \sqrt{n}^{a_1}\sqrt{n}^{a_2}\cdots \sqrt{n}^{a_k} .

    What can we conclude from this?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868
    If the positive number,n, is composite, then there exist integers a and b such that ab= n. If both a and b were larger than \sqrt{n} then n= ab> (\sqrt{n})(\sqrt{n})> which is impossible. That is either a or b is less than n. We can, without loss of generality, assume it is a that is less than n. If a is prime, we are done. If a is not prime, then it has prime factors that are less than a and so less than \sqrt{n}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Thanks! Makes a lot more sense!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 12:23 PM
  2. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  3. Prove a large number is prime
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 1st 2011, 11:17 PM
  4. Find prime divisor
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 20th 2010, 10:04 AM
  5. Least prime number divisor of 5^3 + 9^3
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 14th 2007, 07:15 AM

Search Tags


/mathhelpforum @mathhelpforum