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...

Printable View

- December 6th 2009, 02:41 PMkeityoWriting 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... - December 6th 2009, 02:46 PMVonNemo19
- December 6th 2009, 04:19 PMBruno J.
Here is a proof by induction, using relatively heavy machinery. It clearly holds for by assumption. Suppose you want to write as a sum of distinct primes, and that you have managed to write all numbers up to as a sum of distinct primes. By Bertrand's postulate, there is a prime . Then . Now write as a sum of distinct primes, say . Clearly none of the 's are equal to because and . Thus is a representation of as a sum of distinct primes.

- December 12th 2009, 08:56 AMchiph588@
Aside from your base case, you didn't use the fact that was considered a prime. Therefore if we started at we could have the same theorem without considering as a prime. But is the only way to write as a sum of distinct primes.

With that said, could you explain where else you used as a prime in this proof? - December 12th 2009, 04:52 PMBruno J.
Throughout the proof I supposed 1 as prime, and the assumption is necessary when we want to write as a sum of distinct primes because we could very well have as you noticed.

- December 13th 2009, 09:56 AMwonderboy1953Can'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. - December 13th 2009, 10:20 AMchiph588@
Goldbach's Conjecture doesn't consider the distinctness of the primes being summed though.

- December 13th 2009, 10:37 AMMoo
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 - December 13th 2009, 11:41 AMwonderboy1953Distinctiveness
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.

- December 13th 2009, 01:22 PMBruno J.
- December 13th 2009, 01:25 PMBruno J.
- December 13th 2009, 01:49 PMchiph588@
- December 13th 2009, 06:26 PMShanks
Bruno, is the Bertrand's postulate proved or not yet?

- December 13th 2009, 08:36 PMBruno J.
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. - December 16th 2009, 09:06 AMwonderboy1953Skip 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).