Results 1 to 6 of 6

Math Help - Proofs involving composite numbers

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    13

    Unhappy Proofs involving composite numbers

    1) Prove that every composite number greater than 1 has at least one prime divisor.

    To me, this sounds like the fundamental theorem of arithmetic (I could be dead wrong) and I have found various sites explaining that there are 2 parts to this proof...but I'm not sure if this is how I'm supposed to set it up.

    2) Prove that every composite number n has at least one prime divisor which is =< sqrt(n).

    3) Prove that every composite number can be represented as a product of primes.

    The problem I'm having is that all these proofs seem very alike to me and I don't really know how to begin any of them. I know that every composite number can be broken down into a product of primes,but I don't really know how to show that explicitly.

    Any help would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    #1: Let n be the smallest integer with no prime divisors. Since n is composite, we know that: n = ab where 1 < a,b < n. But since n was the smallest integer with no prime divisors, then there exists some prime such that p \mid a. See the contradiction?

    #2: Let n = ab and 1 < a \leq b < n. Suppose a > \sqrt{n} (so b > \sqrt{n} as well). What can you say about ab then? How would you then bring the prime p into this?

    #3: This is pretty much the fundamental theorem of arithmetic (except for the uniqueness part). Again, we have another proof by contradiction. Suppose n was the smallest number that couldn't be written as a product of primes. It must be composite (otherwise it would be prime!), i.e. n=ab. But since n was the smallest such number, then a and b can be written as a product of primes. Can you piece all these together?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    13
    [QUOTE=o_O;287440]#1: Let n be the smallest integer with no prime divisors. Since n is composite, we know that: n = ab where 1 < a,b < n. But since n was the smallest integer with no prime divisors, then there exists some prime such that p \mid a. See the contradiction?

    Hi, thanks for the quick reply. I still am a little confused. Let me begin with #1.

    It seems like to me that they key to this proof is the fact that 1<a,b<n...because then this tells us that n is not the smallest integer. Which then allows us to conclude that there is some prime number that divides a...so there is a contradiction. I don't really get the last part (meaning, how did we get to the fact that p|a from the fact that n is not the smallest integer anymore?)

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jusstjoe View Post
    how did we get to the fact that p|a from the fact that n is not the smallest integer anymore?
    note that a and b are smaller than n. since n is the smallest integer with no prime divisors, it means that all integers smaller than it have prime divisors (otherwise, one of those integers would have been the smallest). do you see?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    13
    #2: Let n = ab and 1 < a \leq b < n. Suppose a > \sqrt{n} (so b > \sqrt{n} as well). What can you say about ab then? How would you then bring the prime p into this?

    OK.

    So I think given this situation, ab>n? I believe this is so because if a and b are both bigger than sqrt(n), then it must be that a*b>n,
    but then this is a contradiction to our original statement, n=ab...but I don't know if I know how to bring prime numbers into this mix.

    Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jusstjoe View Post
    #2: Let n = ab and 1 < a \leq b < n. Suppose a > \sqrt{n} (so b > \sqrt{n} as well). What can you say about ab then? How would you then bring the prime p into this?

    OK.

    So I think given this situation, ab>n? I believe this is so because if a and b are both bigger than sqrt(n), then it must be that a*b>n,
    but then this is a contradiction to our original statement, n=ab...but I don't know if I know how to bring prime numbers into this mix.

    Thanks for your help.
    think of what we said in #1. that whole p|a thing...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] problem involving composite functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 15th 2011, 08:05 AM
  2. Composite numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2010, 09:39 PM
  3. composite function involving word problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 8th 2009, 06:59 PM
  4. Proofs: Domain of composite functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 20th 2009, 03:49 PM
  5. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2007, 08:41 AM

Search Tags


/mathhelpforum @mathhelpforum