Results 1 to 8 of 8

Math Help - Proof that all numbers>1 are divisable by a prime.

  1. #1
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200

    Proof that all numbers>1 are divisable by a prime.

    I'm trying really hard to get good at making proofs. It is extremely hard for me, much more so than anything else I have ever done. I've tried to prove the title above but I don't know if my proof is logical.

    lemma: "If n > 1 then there is a prime p such that p | n ."
    n and k are integers.

    proof:
    Assume that there is no such p for n>1 such that \frac{n}{p}=k

    This would imply that pk\neq n for any prime value of p.
    This also implies that there are no primes that can be expressed as the division of two integers. p\neq \frac{n}{k}.
    However if this was true, prime numbers would be irrational which they are not.

    Therefore all numbers>1 are divisable by a prime?
    -------------------------------------------------------------------------
    I'm not sure if this is logical. If it is not please don't post the proof, just give me a hint?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,677
    Thanks
    1499

    Re: Proof that all numbers>1 are divisable by a prime.

    Quote Originally Posted by integral View Post
    I'm trying really hard to get good at making proofs. It is extremely hard for me, much more so than anything else I have ever done. I've tried to prove the title above but I don't know if my proof is logical.

    lemma: "If n > 1 then there is a prime p such that p | n ."
    n and k are integers.

    proof:
    Assume that there is no such p for n>1 such that \frac{n}{p}=k

    This would imply that pk\neq n for any prime value of p.
    This also implies that there are no primes that can be expressed as the division of two integers. p\neq \frac{n}{k}.
    However if this was true, prime numbers would be irrational which they are not.

    Therefore all numbers>1 are divisable by a prime?
    -------------------------------------------------------------------------
    I'm not sure if this is logical. If it is not please don't post the proof, just give me a hint?
    If n itself is prime, it can be divided by itself, so can be divided by a prime.

    If n is composite, it is the product of prime factors. So it can be divided by a prime.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200

    Re: Proof that all numbers>1 are divisable by a prime.

    I'm trying to assume I don't know the FTA. :/
    So my proof is wrong?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,677
    Thanks
    1499

    Re: Proof that all numbers>1 are divisable by a prime.

    Quote Originally Posted by integral View Post
    I'm trying to assume I don't know the FTA. :/
    So my proof is wrong?
    What's the FTA? This is basic knowledge of numbers - a positive integer greater than 1 is always either prime or composite...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200

    Re: Proof that all numbers>1 are divisable by a prime.

    Funamental theorem of arithmatic.
    "
    If n is composite, it is the product of prime factors. So it can be divided by a prime." This statement is essentially what I am trying to prove,


    EDIT: Fundamental theorem of arithmatic
    Last edited by integral; July 13th 2011 at 11:42 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,677
    Thanks
    1499

    Re: Proof that all numbers>1 are divisable by a prime.

    Quote Originally Posted by integral View Post
    Funamental theorem of algebra.
    "
    If n is composite, it is the product of prime factors. So it can be divided by a prime." This statement is essentially what I am trying to prove,
    That's what a composite number is defined as - it doesn't need proof...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200

    Re: Proof that all numbers>1 are divisable by a prime.

    A composite number n is defined to be a number divisable a by 1,n, and k where k is some integer.
    A composite number is NOT defined as the product of primes. That is the fundamental theorem of arithmatic which has many proofs "it doesn't need proof..."


    EDIT: Fundamental theorem of arithmatic.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Proof that all numbers>1 are divisable by a prime.

    Quote Originally Posted by integral View Post
    A composite number n is defined to be a number divisable a by 1,n, and k where k is some integer.
    A composite number is NOT defined as the product of primes. That is the fundamental theorem of arithmatic which has many proofs "it doesn't need proof..."


    EDIT: Fundamental theorem of arithmatic.
    i see your dilemma. might i suggest you can proceed by strong induction? 2 is prime (base case).

    now, we assume that for all 1 < k < n, k is divisible by a prime.

    if n is prime, it is divisible by a prime, so assume n is composite. so n is divisible by r, where 1 < r < n.

    by our assumption, r is divisible by some prime, say p, whence n is also divisible by p.

    (the idea is: we know that if a number isn't prime, it has smaller factors. examining these smaller factors,

    they may turn out to be prime, or not, but if not, then they have "smaller smaller factors". this process has to terminate

    at some point, because the number of "smaller numbers" is finite, for any given n).

    the fundamental theorem of arithmetic actually says more than just: any (non-negative integer) number is the product of prime factors. it says that

    the set of factors is UNIQUE, and that the maximum power of any prime factor that divides n is likewise unique.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving prime numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 7th 2011, 02:38 PM
  2. proof with perfect and prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2010, 07:46 PM
  3. Proof relating to prime numbers
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: January 13th 2010, 11:31 AM
  4. Proof relating to prime numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 13th 2010, 10:02 AM
  5. Proof with prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2009, 08:58 PM

Search Tags


/mathhelpforum @mathhelpforum