Prove by contradiction that every integer greater than 11 is a sum of two composite numbers
$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.
elementary-number-theory
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
$endgroup$
add a comment |
$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.
elementary-number-theory
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
$endgroup$
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$
– Ross Millikan
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
add a comment |
$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.
elementary-number-theory
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
$endgroup$
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.
elementary-number-theory
elementary-number-theory
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
asked Jul 24 '13 at 8:59
dotslashdotslash
95721327
95721327
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$
– Ross Millikan
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
add a comment |
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$
– Ross Millikan
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
2
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
$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
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$
(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$
– Ross Millikan
Feb 10 '15 at 16:48
$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$
– Ross Millikan
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
$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
add a comment |
4 Answers
4
active
oldest
votes
$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$.
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
$endgroup$
1
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
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$
– David Durrleman
Feb 12 '15 at 20:17
|
show 3 more comments
$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 $kgeq5$. hence $n = 2(k -4) +9$.
Thus any number $> 11$ can be expressed as the sum of two composite numbers!!
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
$endgroup$
add a comment |
$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 $ngeq 30$, a contradiction.
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
$endgroup$
$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$
– Ross Millikan
Dec 18 '16 at 14:43
add a comment |
$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.
answered Dec 10 '14 at 23:46
d williamsd williams
11
$endgroup$
$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$
– Chantry Cargill
Dec 10 '14 at 23:49
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f450930%2fprove-by-contradiction-that-every-integer-greater-than-11-is-a-sum-of-two-compos%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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$.
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
$endgroup$
1
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
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$
– David Durrleman
Feb 12 '15 at 20:17
|
show 3 more comments
$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$.
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
$endgroup$
1
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
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$
– David Durrleman
Feb 12 '15 at 20:17
|
show 3 more comments
$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$.
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
$endgroup$
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$.
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
answered Jul 24 '13 at 9:01
Andreas CarantiAndreas Caranti
56.5k34395
56.5k34395
1
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
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$
– David Durrleman
Feb 12 '15 at 20:17
|
show 3 more comments
1
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
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$
– David Durrleman
Feb 12 '15 at 20:17
1
1
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
Spoiler #4 >! nice spoiler(+1)
$endgroup$
– user63181
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
@SamiBenRomdhane, thanks!
$endgroup$
– Andreas Caranti
Jul 24 '13 at 9:07
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
This is great! But where does this involve proof by contradiction?
$endgroup$
– dotslash
Jul 24 '13 at 9:26
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
Jul 24 '13 at 9:36
$begingroup$
It doesn't. So what? Why do you care how it's proved?
$endgroup$
– Gerry Myerson
Jul 24 '13 at 9:36
1
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$
– David Durrleman
Feb 12 '15 at 20:17
$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$
– David Durrleman
Feb 12 '15 at 20:17
|
show 3 more comments
$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 $kgeq5$. hence $n = 2(k -4) +9$.
Thus any number $> 11$ can be expressed as the sum of two composite numbers!!
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
$endgroup$
add a comment |
$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 $kgeq5$. hence $n = 2(k -4) +9$.
Thus any number $> 11$ can be expressed as the sum of two composite numbers!!
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
$endgroup$
add a comment |
$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 $kgeq5$. hence $n = 2(k -4) +9$.
Thus any number $> 11$ can be expressed as the sum of two composite numbers!!
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
$endgroup$
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 $kgeq5$. hence $n = 2(k -4) +9$.
Thus any number $> 11$ can be expressed as the sum of two composite numbers!!
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
answered Feb 10 '15 at 16:28
user8795user8795
5,66962047
5,66962047
add a comment |
add a comment |
$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 $ngeq 30$, a contradiction.
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
$endgroup$
$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$
– Ross Millikan
Dec 18 '16 at 14:43
add a comment |
$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 $ngeq 30$, a contradiction.
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
$endgroup$
$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$
– Ross Millikan
Dec 18 '16 at 14:43
add a comment |
$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 $ngeq 30$, a contradiction.
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
$endgroup$
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 $ngeq 30$, a contradiction.
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
edited Dec 18 '16 at 14:35
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
answered Dec 18 '16 at 14:13
MathelogicianMathelogician
5610
5610
$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$
– Ross Millikan
Dec 18 '16 at 14:43
add a comment |
$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$
– Ross Millikan
Dec 18 '16 at 14:43
$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$
– Ross Millikan
Dec 18 '16 at 14:43
$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$
– Ross Millikan
Dec 18 '16 at 14:43
add a comment |
$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.
answered Dec 10 '14 at 23:46
d williamsd williams
11
$endgroup$
$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$
– Chantry Cargill
Dec 10 '14 at 23:49
add a comment |
$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.
answered Dec 10 '14 at 23:46
d williamsd williams
11
$endgroup$
$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$
– Chantry Cargill
Dec 10 '14 at 23:49
add a comment |
$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.
answered Dec 10 '14 at 23:46
d williamsd williams
11
$endgroup$
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.
answered Dec 10 '14 at 23:46
d williamsd williams
11
edited Dec 10 '14 at 23:55
answered Dec 10 '14 at 23:46
d williamsd williams
11
answered Dec 10 '14 at 23:46
d williamsd williams
11
answered Dec 10 '14 at 23:46
d williamsd williams
11
11
$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$
– Chantry Cargill
Dec 10 '14 at 23:49
add a comment |
$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$
– Chantry Cargill
Dec 10 '14 at 23:49
$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
$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
2
$begingroup$
For some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– Chantry Cargill
Dec 10 '14 at 23:49
$begingroup$
For some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– Chantry Cargill
Dec 10 '14 at 23:49
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f450930%2fprove-by-contradiction-that-every-integer-greater-than-11-is-a-sum-of-two-compos%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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$
– Ross Millikan
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