Page 1 of 2 12 LastLast
Results 1 to 15 of 17
Like Tree1Thanks

Math Help - Writing numbers as sum of primes

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    22

    Writing numbers as sum of primes

    For this problem include 1 as a prime. Prove that every positive integer can be written as a sum of one or more distinct primes.

    I'm a bit stumped...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823
    Quote Originally Posted by keityo View Post
    For this problem include 1 as a prime. Prove that every positive integer can be written as a sum of one or more distinct primes.

    I'm a bit stumped...
    Having 1 included is nice.

    Note that the odd natural numbers can be written as

    2n+1

    And the evens

    2n+2.

    Taken together, the odds and evens make the naturals.

    And there you have it. I'm sure that you can formalize this argument.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Here is a proof by induction, using relatively heavy machinery. It clearly holds for n=1 by assumption. Suppose you want to write n as a sum of distinct primes, and that you have managed to write all numbers up to n-1 as a sum of distinct primes. By Bertrand's postulate, there is a prime n \geq p >n/2. Then n-p < n/2. Now write n-p as a sum of distinct primes, say n-p=p_1+...+p_k. Clearly none of the p_j's are equal to p because p>n/2 and n-p<n/2. Thus n=p+p_1+...+p_k is a representation of n as a sum of distinct primes. \square
    Thanks from keityo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bruno J. View Post
    Here is a proof by induction, using relatively heavy machinery. It clearly holds for n=1 by assumption. Suppose you want to write n as a sum of distinct primes, and that you have managed to write all numbers up to n-1 as a sum of distinct primes. By Bertrand's postulate, there is a prime n \geq p >n/2. Then n-p < n/2. Now write n-p as a sum of distinct primes, say n-p=p_1+...+p_k. Clearly none of the p_j's are equal to p because p>n/2 and n-p<n/2. Thus n=p+p_1+...+p_k is a representation of n as a sum of distinct primes. \square
    Aside from your base case, you didn't use the fact that  1 was considered a prime. Therefore if we started at  n=2 we could have the same theorem without considering  1 as a prime. But  4=3+1 is the only way to write  4 as a sum of distinct primes.
    With that said, could you explain where else you used  1 as a prime in this proof?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Throughout the proof I supposed 1 as prime, and the assumption is necessary when we want to write n-p as a sum of distinct primes because we could very well have n-p=1 as you noticed.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    769

    Can't be proven

    "Prove that every positive integer can be written as a sum of one or more distinct primes"

    Consider the even numbers. Goldbach's conjecture says that every even number can be written as the sum of primes. Problem here is that no one has yet proven Goldbach's conjecture.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Goldbach's Conjecture doesn't consider the distinctness of the primes being summed though.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Otherwise, without including 1 as a prime, you can make it as a sum of 2's (for even numbers) or a sum of 2's+3 (for odd numbers)

    :P
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    769

    Distinctiveness

    Implicitly, Goldbach's Conjecture does consider distinctiveness because, besides 2, every even number 4 or greater when divided by 2, yields only even numbers which can't be prime so the only other choice for possible prime numbers must be distinct numbers.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    "Prove that every positive integer can be written as a sum of one or more distinct primes"

    Consider the even numbers. Goldbach's conjecture says that every even number can be written as the sum of two primes. Problem here is that no one has yet proven Goldbach's conjecture.
    Fixed!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    Implicitly, Goldbach's Conjecture does consider distinctiveness because, besides 2, every even number 4 or greater when divided by 2, yields only even numbers which can't be prime so the only other choice for possible prime numbers must be distinct numbers.
    Huh? Twice an odd number is even; if you divide it by 2 what do you get?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by wonderboy1953 View Post
    Implicitly, Goldbach's Conjecture does consider distinctiveness because, besides 2, every even number 4 or greater when divided by 2, yields only even numbers which can't be prime so the only other choice for possible prime numbers must be distinct numbers.
     4=2+2 is the only way to express  4 as the sum of primes.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Bruno, is the Bertrand's postulate proved or not yet?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Of course! Or else I would have never used it to prove something else.
    It was first proven by Chebyshev and then by Erdös in a more elementary fashion.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Banned
    Joined
    Oct 2009
    Posts
    769

    Skip Goldbach's Conjecture

    Goldbach"s Conjecture says every positive integer above 1 (counting 1 as a prime number) can be written as the sum of two prime numbers while Keityo puts forth the problem as "Prove that every positive integer can be written as a sum of one or more distinct primes." This lets out Goldbach's Conjecture as applying to this problem (I get onto the internet from my library which has a time restriction so I didn't get a chance to carefully review what I've written - sorry about that).
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Writing the sum of two square numbers?
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: March 13th 2011, 04:27 PM
  2. Writing a number in terms of other numbers.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 15th 2010, 08:31 PM
  3. Writing the Numbers till N to form a new number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2009, 02:17 AM
  4. Writing complex numbers in the form x+ij.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: December 6th 2008, 06:04 AM
  5. Euclid's theorem and primes numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2006, 08:33 AM

Search Tags


/mathhelpforum @mathhelpforum