15
$\begingroup$

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.

$\endgroup$
4
  • 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, 2013 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, 2013 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, 2015 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, 2016 at 14:52

4 Answers 4

18
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ This is great! But where does this involve proof by contradiction? $\endgroup$
    – ankush981
    Jul 24, 2013 at 9:26
  • $\begingroup$ It doesn't. So what? Why do you care how it's proved? $\endgroup$ Jul 24, 2013 at 9:36
  • $\begingroup$ @Gerry Presumably because that's what's written in the textbook OP mentions (why it would say it wants a proof by contradiction given the nature of its hint I don't understand). $\endgroup$
    – anon
    Jul 24, 2013 at 10:51
  • $\begingroup$ @GerryMyerson The textbook wants a proof by contradiction. Anyway, it's good enough for me. $\endgroup$
    – ankush981
    Jul 24, 2013 at 13:43
  • 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, 2015 at 20:17
8
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2016 at 14:43
-2
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2014 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, 2014 at 23:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .