I have thought a lot but am failing to arrive at anything encouraging.

First try: If this is to be proved by contradiction, then I start with the assumption that let $n$ be a number which is a sum of two numbers, of which at least one is prime. This gives $n = p + c$, where $p$ is the prime number and $c$ is the composite number. Also, any composite number can be written as a product of primes. So I can say, $n = p + p_1^{e_1}.p_2^{e_2}...p_k^{e_k}$. From this, I get $n - p = p_1^{e_1}.p_2^{e_2}...p_k^{e_k}$, but I have no clue what to do next.

Second try: For an instant let me forget about contradiction. Since $n > 11$, I can say that $n \geq 12$. This means that either $p \geq 6$ or $c \geq 6$. Again I'm not sure what to do next.

Finally, consider that the number 20 can be expressed in three different ways: $17+3$ (both prime), $16+4$ (both composite), and $18+2$ (one prime and one composite). This makes me wonder what we are trying to prove.

The textbook contains a hint, "Can all three of $n-4$, $n-6$, $n-8$ be prime?", but I'm sure what's so special about $4, 6, 8$ here.

  • 2
    $\begingroup$ At least one of the three numbers $n-4$, $n-6$, $n-8$ is divisible by a certain prime... $\endgroup$
    – anon
    Jul 24 '13 at 9:08
  • 1
    $\begingroup$ (what we are trying to prove is that it exists at least one way to write a number greater than 11 as the sum of two composite numbers. You may partition it in many different ways: what matters is, at least one partition uses two composite numbers) $\endgroup$
    – mau
    Jul 24 '13 at 10:15
  • $\begingroup$ In your first try, you should say that $n$ is a number such that for every way of expressing it as a sum, at least one number is prime. For example, $12$ satisfies what you say, because $12=9+3$ and $3$ is prime. You then cannot assume the sum includes a composite-both numbers can be prime. Neither of these observations go to the heart of the problem. $\endgroup$ Feb 10 '15 at 16:48
  • $\begingroup$ A hint different from the text's: Suppose the statement is false and look at the smallest counterexample n.. Since 12= 8+4 13= 9 +4 14 =8+6 and 15= 9+6, n is greater than 16. $\endgroup$
    – Airymouse
    Dec 18 '16 at 14:52

Spoiler #1

You can write $n = (n - \varepsilon) + \varepsilon$, where $\varepsilon \in \{4, 6, 8\}$.

Spoiler #2

$n - \varepsilon > 3$, as $n > 11$.

Spoiler #3

One of the three numbers $n - \varepsilon$ is divisible by $3$, as they are distinct modulo $3$.

  • 1
    $\begingroup$ Spoiler #4 >! nice spoiler(+1) $\endgroup$
    – user63181
    Jul 24 '13 at 9:07
  • $\begingroup$ @SamiBenRomdhane, thanks! $\endgroup$ Jul 24 '13 at 9:07
  • $\begingroup$ This is great! But where does this involve proof by contradiction? $\endgroup$
    – ankush981
    Jul 24 '13 at 9:26
  • $\begingroup$ It doesn't. So what? Why do you care how it's proved? $\endgroup$ Jul 24 '13 at 9:36
  • 1
    $\begingroup$ Writing the same proof with $\varepsilon \in \{8,9\}$ makes it even more obvious (everyone knows that for any $p>2$, either $p$ or $p+1$ is an even composite) $\endgroup$ Feb 12 '15 at 20:17

How about this solution??

If $n$ is even, then $n$ is of the form $2k$ where $k \geq 6$. Hence $n = 2(k-4) +8$.

And if $n$ is odd, then $n$ is of the form $2k+1$ where $k\geq5$. hence $n = 2(k -4) +9$.

Thus any number $> 11$ can be expressed as the sum of two composite numbers!!


Let's say that integer $n>11$ can't be expressed as the sum of two composite numbers. Then:

  • $n=a+p$ (p is a prime and a is a composite or prime number)

Even numbers that greater than $2$ are composite.

The number of even numbers that smaller or equal to $n$ is $[\frac{n-2}{2}]$(Why?).

We said that $n$ can't be expressed as sum two composite numbers, then there have to be $[\frac{n-2}{2}]$ prime numbers at least(Why?).

But this result can't hold for $n\geq 30$, a contradiction.

  • $\begingroup$ You still have to close the gap between $12$ and $29$ You can do that by exhaustion easily enough, but it needs to be done. $\endgroup$ Dec 18 '16 at 14:43

Only 9 even numbers greater than 4 can't be expressed as the ORDERED sum of two ODD composites, namely 6, 8, 10, 12, 14, 16, 22, 32, 38.

Look at the 4 identities: 1. pp(2n)=pr[2,n]-pc(2n) 2. cc(2n)=c[2,n]-cp(2n) 3. pp(2n)=pr[n,2n-2]-cp(2n) 4. cc(2n)=c[n,2n-2]-pc(2n)

where pp(2n)=number of ordered sum of 2 primes = 2n, cc(2n)=# of ordered sums of 2 composites=2n, cp(2n)=number of ordered sums of 1 composite and 1 prime (in that order)=2n, and pc(2n)= number of ordered sums of 1 prime and 1 composite (in that order)=2n, and a+b is an ordered sum iff a< or = to b, pr[a,b] = number of primes in[a,b], c[a,b] = number of composites in [a,b]

Lots of other identities to construct from the 4 above - have fun playing with.

  • $\begingroup$ and: pr[a,b] = the number of primes in [a,b] and c[a,b]= the number of composites in [a,b] $\endgroup$
    – d williams
    Dec 10 '14 at 23:48
  • 2
    $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$
    – user109879
    Dec 10 '14 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.