What is wrong with my proof by contradiction that if $n^2$ is divisible by 3, then $n^2$ is divisible by 9?
$begingroup$
I'm working through the book Language, Proof and Logic (2nd ed., Barker-Plummer, Barwise & Etchemendy). This is problem 5.25, presented right after the introduction to proof by contradiction.
Prompt: Assume that $n^2$ is divisible by 3. Prove that $n^2$ is divisible by 9.
Here's my take on it:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 9m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(3m)$.
- From 1, 3, we have $k neq 3m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 9m text{ (for a non-zero integer m)}$.
The problem is that, I don't think this is right because I can replace 9 with 81 and do:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 81m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(27m)$.
- From 1, 3, we have $k neq 27m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 81m text{ (for a non-zero integer m)}$. Which I can refute giving a counter example n = 3.
I don't think this chapter restrict me to using only proofs by contradiction, but it only allows me to use basic arithmetics and definitions of even / odd (and also prove by cases). I think this answer should satisfy the requirement by the book.
Yet, I'm curious about what is wrong about my way of proving by contradiction?
elementary-number-theory proof-verification
edited Dec 28 '18 at 6:38
Shaun
9,544113684
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
$endgroup$
add a comment |
$begingroup$
I'm working through the book Language, Proof and Logic (2nd ed., Barker-Plummer, Barwise & Etchemendy). This is problem 5.25, presented right after the introduction to proof by contradiction.
Prompt: Assume that $n^2$ is divisible by 3. Prove that $n^2$ is divisible by 9.
Here's my take on it:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 9m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(3m)$.
- From 1, 3, we have $k neq 3m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 9m text{ (for a non-zero integer m)}$.
The problem is that, I don't think this is right because I can replace 9 with 81 and do:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 81m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(27m)$.
- From 1, 3, we have $k neq 27m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 81m text{ (for a non-zero integer m)}$. Which I can refute giving a counter example n = 3.
I don't think this chapter restrict me to using only proofs by contradiction, but it only allows me to use basic arithmetics and definitions of even / odd (and also prove by cases). I think this answer should satisfy the requirement by the book.
Yet, I'm curious about what is wrong about my way of proving by contradiction?
elementary-number-theory proof-verification
edited Dec 28 '18 at 6:38
Shaun
9,544113684
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
$endgroup$
$begingroup$
You might try replacing $n^2$ with $6$ everywhere in your argument to understand what's wrong. (Yes, $6$ isn't a square, but you never used the fact that $n^2$ is a square.)
$endgroup$
– Eric Wofsey
Dec 28 '18 at 6:26
$begingroup$
This is a high quality question. It includes many details about your thoughts on the problem. Thus I think it deserves more upvotes.
$endgroup$
– Shaun
Dec 28 '18 at 6:39
$begingroup$
By the way, if you'd like a proof now the error has been explained, look at the residue classes of $n^2$ modulo $3$ that follow from each option for $n$ to prove by contradiction $3|n^2implies 3|n$, so you can write $n=3kimplies n^2=9k^2$.
$endgroup$
– J.G.
Dec 28 '18 at 7:44
1
$begingroup$
@Shaun I agree, we need more of this here. +1
$endgroup$
– Randall
Dec 28 '18 at 13:33
add a comment |
$begingroup$
I'm working through the book Language, Proof and Logic (2nd ed., Barker-Plummer, Barwise & Etchemendy). This is problem 5.25, presented right after the introduction to proof by contradiction.
Prompt: Assume that $n^2$ is divisible by 3. Prove that $n^2$ is divisible by 9.
Here's my take on it:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 9m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(3m)$.
- From 1, 3, we have $k neq 3m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 9m text{ (for a non-zero integer m)}$.
The problem is that, I don't think this is right because I can replace 9 with 81 and do:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 81m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(27m)$.
- From 1, 3, we have $k neq 27m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 81m text{ (for a non-zero integer m)}$. Which I can refute giving a counter example n = 3.
I don't think this chapter restrict me to using only proofs by contradiction, but it only allows me to use basic arithmetics and definitions of even / odd (and also prove by cases). I think this answer should satisfy the requirement by the book.
Yet, I'm curious about what is wrong about my way of proving by contradiction?
elementary-number-theory proof-verification
edited Dec 28 '18 at 6:38
Shaun
9,544113684
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
$endgroup$
I'm working through the book Language, Proof and Logic (2nd ed., Barker-Plummer, Barwise & Etchemendy). This is problem 5.25, presented right after the introduction to proof by contradiction.
Prompt: Assume that $n^2$ is divisible by 3. Prove that $n^2$ is divisible by 9.
Here's my take on it:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 9m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(3m)$.
- From 1, 3, we have $k neq 3m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 9m text{ (for a non-zero integer m)}$.
The problem is that, I don't think this is right because I can replace 9 with 81 and do:
- Assume that $n^2 = 3k text{ (k being any non-zero integer)}$
- Let $n^2 neq 81m text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
- From 2, $n^2 neq 3(27m)$.
- From 1, 3, we have $k neq 27m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 81m text{ (for a non-zero integer m)}$. Which I can refute giving a counter example n = 3.
I don't think this chapter restrict me to using only proofs by contradiction, but it only allows me to use basic arithmetics and definitions of even / odd (and also prove by cases). I think this answer should satisfy the requirement by the book.
Yet, I'm curious about what is wrong about my way of proving by contradiction?
elementary-number-theory proof-verification
elementary-number-theory proof-verification
edited Dec 28 '18 at 6:38
Shaun
9,544113684
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
edited Dec 28 '18 at 6:38
Shaun
9,544113684
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
edited Dec 28 '18 at 6:38
Shaun
9,544113684
edited Dec 28 '18 at 6:38
Shaun
9,544113684
edited Dec 28 '18 at 6:38
Shaun
9,544113684
9,544113684
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
asked Dec 28 '18 at 6:13
potasmicpotasmic
1335
1335
$begingroup$
You might try replacing $n^2$ with $6$ everywhere in your argument to understand what's wrong. (Yes, $6$ isn't a square, but you never used the fact that $n^2$ is a square.)
$endgroup$
– Eric Wofsey
Dec 28 '18 at 6:26
$begingroup$
This is a high quality question. It includes many details about your thoughts on the problem. Thus I think it deserves more upvotes.
$endgroup$
– Shaun
Dec 28 '18 at 6:39
$begingroup$
By the way, if you'd like a proof now the error has been explained, look at the residue classes of $n^2$ modulo $3$ that follow from each option for $n$ to prove by contradiction $3|n^2implies 3|n$, so you can write $n=3kimplies n^2=9k^2$.
$endgroup$
– J.G.
Dec 28 '18 at 7:44
1
$begingroup$
@Shaun I agree, we need more of this here. +1
$endgroup$
– Randall
Dec 28 '18 at 13:33
add a comment |
$begingroup$
You might try replacing $n^2$ with $6$ everywhere in your argument to understand what's wrong. (Yes, $6$ isn't a square, but you never used the fact that $n^2$ is a square.)
$endgroup$
– Eric Wofsey
Dec 28 '18 at 6:26
$begingroup$
This is a high quality question. It includes many details about your thoughts on the problem. Thus I think it deserves more upvotes.
$endgroup$
– Shaun
Dec 28 '18 at 6:39
$begingroup$
By the way, if you'd like a proof now the error has been explained, look at the residue classes of $n^2$ modulo $3$ that follow from each option for $n$ to prove by contradiction $3|n^2implies 3|n$, so you can write $n=3kimplies n^2=9k^2$.
$endgroup$
– J.G.
Dec 28 '18 at 7:44
1
$begingroup$
@Shaun I agree, we need more of this here. +1
$endgroup$
– Randall
Dec 28 '18 at 13:33
$begingroup$
You might try replacing $n^2$ with $6$ everywhere in your argument to understand what's wrong. (Yes, $6$ isn't a square, but you never used the fact that $n^2$ is a square.)
$endgroup$
– Eric Wofsey
Dec 28 '18 at 6:26
$begingroup$
You might try replacing $n^2$ with $6$ everywhere in your argument to understand what's wrong. (Yes, $6$ isn't a square, but you never used the fact that $n^2$ is a square.)
$endgroup$
– Eric Wofsey
Dec 28 '18 at 6:26
$begingroup$
This is a high quality question. It includes many details about your thoughts on the problem. Thus I think it deserves more upvotes.
$endgroup$
– Shaun
Dec 28 '18 at 6:39
$begingroup$
This is a high quality question. It includes many details about your thoughts on the problem. Thus I think it deserves more upvotes.
$endgroup$
– Shaun
Dec 28 '18 at 6:39
$begingroup$
By the way, if you'd like a proof now the error has been explained, look at the residue classes of $n^2$ modulo $3$ that follow from each option for $n$ to prove by contradiction $3|n^2implies 3|n$, so you can write $n=3kimplies n^2=9k^2$.
$endgroup$
– J.G.
Dec 28 '18 at 7:44
$begingroup$
By the way, if you'd like a proof now the error has been explained, look at the residue classes of $n^2$ modulo $3$ that follow from each option for $n$ to prove by contradiction $3|n^2implies 3|n$, so you can write $n=3kimplies n^2=9k^2$.
$endgroup$
– J.G.
Dec 28 '18 at 7:44
1
1
$begingroup$
@Shaun I agree, we need more of this here. +1
$endgroup$
– Randall
Dec 28 '18 at 13:33
$begingroup$
@Shaun I agree, we need more of this here. +1
$endgroup$
– Randall
Dec 28 '18 at 13:33
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
"Assume that $n^2 = 3k$ ($k$ being any non-zero integer)."
There is the problem. $k$ is some integer. Since $n^2$ is a fixed number, $k$ cannot be anything you want.
The place where you attempt to reach a contraction, "But we have previously said that $k$ can be any non-zero integer" therefore doesn't work.
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
$endgroup$
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
add a comment |
$begingroup$
I think your conclusion 4 is not correct in the first case and the statement 1 should be
there exists k such that $n^2$=3*k (where k belongs to integer)
Now coming into the actual proof:-
we have 3 divides $n^2$
implies, 3 divides n (*)
implies 9 divides $n^2$
The statement marked in (*) can be proved trivially by contradiction
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
$endgroup$
add a comment |
$begingroup$
You should be saying $k$ is a fixed, nonzero integer (not $k$ is any nonzero integer).
Your proof is incorrect. You didn't get a contradiction.
To do this, I think you need Euclid's lemma: $pmid abimplies pmid alor pmid b$.
Or perhaps the prime factorization.
So suppose that $3mid n^2$. By Euclid's lemma, $3mid n$. So $n=3k$ for some $k$. Then $n^2=(3k)^2=9k^2$. Hence $9mid n^2$.
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
$endgroup$
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
add a comment |
$begingroup$
you say
1.Assume that $n^2=3k$ ($k$ being any non-zero integer)
Obviously you can't mean $k$ can be any non-zero integer. $k$ can't be ... $5$..., say, because $n^2 = 3*5 = 15$ is simply not possible.
$k$ can be any number so that $3k$ is a perfect square or $k$ can be any $frac {n^2}3$ so that $frac {n^2}3$ is an integer but... we really don't at this point of the game have any idea when such numbers are possible and when they are not.
We have to prove that any such $k$ must also be divisible by $3$.
Hint: Consider what happens if $3|n$ or $3 not mid n$. If $3|n$ does $9|n^2$? If $3 not mid n$ does $3|n^2$?
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
$endgroup$
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%2f3054624%2fwhat-is-wrong-with-my-proof-by-contradiction-that-if-n2-is-divisible-by-3-th%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$
"Assume that $n^2 = 3k$ ($k$ being any non-zero integer)."
There is the problem. $k$ is some integer. Since $n^2$ is a fixed number, $k$ cannot be anything you want.
The place where you attempt to reach a contraction, "But we have previously said that $k$ can be any non-zero integer" therefore doesn't work.
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
$endgroup$
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
add a comment |
$begingroup$
"Assume that $n^2 = 3k$ ($k$ being any non-zero integer)."
There is the problem. $k$ is some integer. Since $n^2$ is a fixed number, $k$ cannot be anything you want.
The place where you attempt to reach a contraction, "But we have previously said that $k$ can be any non-zero integer" therefore doesn't work.
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
$endgroup$
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
add a comment |
$begingroup$
"Assume that $n^2 = 3k$ ($k$ being any non-zero integer)."
There is the problem. $k$ is some integer. Since $n^2$ is a fixed number, $k$ cannot be anything you want.
The place where you attempt to reach a contraction, "But we have previously said that $k$ can be any non-zero integer" therefore doesn't work.
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
$endgroup$
"Assume that $n^2 = 3k$ ($k$ being any non-zero integer)."
There is the problem. $k$ is some integer. Since $n^2$ is a fixed number, $k$ cannot be anything you want.
The place where you attempt to reach a contraction, "But we have previously said that $k$ can be any non-zero integer" therefore doesn't work.
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
answered Dec 28 '18 at 6:22
D_SD_S
13.9k61553
13.9k61553
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
add a comment |
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
Ah, I see. If I understand correctly, would I be able to assert "k is some number, but that number is not multiple of three" at step 4?
$endgroup$
– potasmic
Dec 28 '18 at 6:31
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
I don't know. But in order for the proof to work, you have to make use of the fact that $3$ is prime, in some form or other.
$endgroup$
– D_S
Dec 28 '18 at 6:36
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
"would I be able to assert "k is some number, but that number is not multiple of three" at step 4" you can (and must) assert that if you are doing a proof by contradiction. But it might be hard to find the contradiction.
$endgroup$
– fleablood
Dec 28 '18 at 7:52
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
$begingroup$
I think: "[...] but k is not a multiple of 3" --> "But if k isn't a multiple of 3, it can't be a multiple of 9 either" but this doesn't produce a contradiction (it's consistent with contrary of conclusion)... So yeah, I'll solve it another way, but this is interesting nonetheless to tackle it with the hope for contradiction.
$endgroup$
– potasmic
Dec 28 '18 at 8:42
add a comment |
$begingroup$
I think your conclusion 4 is not correct in the first case and the statement 1 should be
there exists k such that $n^2$=3*k (where k belongs to integer)
Now coming into the actual proof:-
we have 3 divides $n^2$
implies, 3 divides n (*)
implies 9 divides $n^2$
The statement marked in (*) can be proved trivially by contradiction
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
$endgroup$
add a comment |
$begingroup$
I think your conclusion 4 is not correct in the first case and the statement 1 should be
there exists k such that $n^2$=3*k (where k belongs to integer)
Now coming into the actual proof:-
we have 3 divides $n^2$
implies, 3 divides n (*)
implies 9 divides $n^2$
The statement marked in (*) can be proved trivially by contradiction
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
$endgroup$
add a comment |
$begingroup$
I think your conclusion 4 is not correct in the first case and the statement 1 should be
there exists k such that $n^2$=3*k (where k belongs to integer)
Now coming into the actual proof:-
we have 3 divides $n^2$
implies, 3 divides n (*)
implies 9 divides $n^2$
The statement marked in (*) can be proved trivially by contradiction
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
$endgroup$
I think your conclusion 4 is not correct in the first case and the statement 1 should be
there exists k such that $n^2$=3*k (where k belongs to integer)
Now coming into the actual proof:-
we have 3 divides $n^2$
implies, 3 divides n (*)
implies 9 divides $n^2$
The statement marked in (*) can be proved trivially by contradiction
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
answered Dec 28 '18 at 6:22
Bijayan RayBijayan Ray
136112
136112
add a comment |
add a comment |
$begingroup$
You should be saying $k$ is a fixed, nonzero integer (not $k$ is any nonzero integer).
Your proof is incorrect. You didn't get a contradiction.
To do this, I think you need Euclid's lemma: $pmid abimplies pmid alor pmid b$.
Or perhaps the prime factorization.
So suppose that $3mid n^2$. By Euclid's lemma, $3mid n$. So $n=3k$ for some $k$. Then $n^2=(3k)^2=9k^2$. Hence $9mid n^2$.
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
$endgroup$
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
add a comment |
$begingroup$
You should be saying $k$ is a fixed, nonzero integer (not $k$ is any nonzero integer).
Your proof is incorrect. You didn't get a contradiction.
To do this, I think you need Euclid's lemma: $pmid abimplies pmid alor pmid b$.
Or perhaps the prime factorization.
So suppose that $3mid n^2$. By Euclid's lemma, $3mid n$. So $n=3k$ for some $k$. Then $n^2=(3k)^2=9k^2$. Hence $9mid n^2$.
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
$endgroup$
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
add a comment |
$begingroup$
You should be saying $k$ is a fixed, nonzero integer (not $k$ is any nonzero integer).
Your proof is incorrect. You didn't get a contradiction.
To do this, I think you need Euclid's lemma: $pmid abimplies pmid alor pmid b$.
Or perhaps the prime factorization.
So suppose that $3mid n^2$. By Euclid's lemma, $3mid n$. So $n=3k$ for some $k$. Then $n^2=(3k)^2=9k^2$. Hence $9mid n^2$.
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
$endgroup$
You should be saying $k$ is a fixed, nonzero integer (not $k$ is any nonzero integer).
Your proof is incorrect. You didn't get a contradiction.
To do this, I think you need Euclid's lemma: $pmid abimplies pmid alor pmid b$.
Or perhaps the prime factorization.
So suppose that $3mid n^2$. By Euclid's lemma, $3mid n$. So $n=3k$ for some $k$. Then $n^2=(3k)^2=9k^2$. Hence $9mid n^2$.
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
edited Dec 28 '18 at 7:13
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
answered Dec 28 '18 at 6:27
Chris CusterChris Custer
14.2k3827
14.2k3827
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
add a comment |
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
I don't think I can touch primes or its property yet at this point. Also, do you mean I can reach a contradiction if I use Euclid's lemma?
$endgroup$
– potasmic
Dec 28 '18 at 6:28
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
Yes. Or you could prove it directly.
$endgroup$
– Chris Custer
Dec 28 '18 at 6:29
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
You need to use primes. Substitue $3$ with $4$ (and $9$ with $16$) and it won't be true. You might manage to avoid the word prime but you will need this property of $3$. A slightly weaker property than prime can work but it is not true of any integer.
$endgroup$
– badjohn
Dec 28 '18 at 7:24
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
$begingroup$
But Euclid's lemma relies on primes.
$endgroup$
– Chris Custer
Dec 28 '18 at 12:10
add a comment |
$begingroup$
you say
1.Assume that $n^2=3k$ ($k$ being any non-zero integer)
Obviously you can't mean $k$ can be any non-zero integer. $k$ can't be ... $5$..., say, because $n^2 = 3*5 = 15$ is simply not possible.
$k$ can be any number so that $3k$ is a perfect square or $k$ can be any $frac {n^2}3$ so that $frac {n^2}3$ is an integer but... we really don't at this point of the game have any idea when such numbers are possible and when they are not.
We have to prove that any such $k$ must also be divisible by $3$.
Hint: Consider what happens if $3|n$ or $3 not mid n$. If $3|n$ does $9|n^2$? If $3 not mid n$ does $3|n^2$?
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
$endgroup$
add a comment |
$begingroup$
you say
1.Assume that $n^2=3k$ ($k$ being any non-zero integer)
Obviously you can't mean $k$ can be any non-zero integer. $k$ can't be ... $5$..., say, because $n^2 = 3*5 = 15$ is simply not possible.
$k$ can be any number so that $3k$ is a perfect square or $k$ can be any $frac {n^2}3$ so that $frac {n^2}3$ is an integer but... we really don't at this point of the game have any idea when such numbers are possible and when they are not.
We have to prove that any such $k$ must also be divisible by $3$.
Hint: Consider what happens if $3|n$ or $3 not mid n$. If $3|n$ does $9|n^2$? If $3 not mid n$ does $3|n^2$?
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
$endgroup$
add a comment |
$begingroup$
you say
1.Assume that $n^2=3k$ ($k$ being any non-zero integer)
Obviously you can't mean $k$ can be any non-zero integer. $k$ can't be ... $5$..., say, because $n^2 = 3*5 = 15$ is simply not possible.
$k$ can be any number so that $3k$ is a perfect square or $k$ can be any $frac {n^2}3$ so that $frac {n^2}3$ is an integer but... we really don't at this point of the game have any idea when such numbers are possible and when they are not.
We have to prove that any such $k$ must also be divisible by $3$.
Hint: Consider what happens if $3|n$ or $3 not mid n$. If $3|n$ does $9|n^2$? If $3 not mid n$ does $3|n^2$?
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
$endgroup$
you say
1.Assume that $n^2=3k$ ($k$ being any non-zero integer)
Obviously you can't mean $k$ can be any non-zero integer. $k$ can't be ... $5$..., say, because $n^2 = 3*5 = 15$ is simply not possible.
$k$ can be any number so that $3k$ is a perfect square or $k$ can be any $frac {n^2}3$ so that $frac {n^2}3$ is an integer but... we really don't at this point of the game have any idea when such numbers are possible and when they are not.
We have to prove that any such $k$ must also be divisible by $3$.
Hint: Consider what happens if $3|n$ or $3 not mid n$. If $3|n$ does $9|n^2$? If $3 not mid n$ does $3|n^2$?
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
answered Dec 28 '18 at 7:49
fleabloodfleablood
72.7k22788
72.7k22788
add a comment |
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%2f3054624%2fwhat-is-wrong-with-my-proof-by-contradiction-that-if-n2-is-divisible-by-3-th%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
$begingroup$
You might try replacing $n^2$ with $6$ everywhere in your argument to understand what's wrong. (Yes, $6$ isn't a square, but you never used the fact that $n^2$ is a square.)
$endgroup$
– Eric Wofsey
Dec 28 '18 at 6:26
$begingroup$
This is a high quality question. It includes many details about your thoughts on the problem. Thus I think it deserves more upvotes.
$endgroup$
– Shaun
Dec 28 '18 at 6:39
$begingroup$
By the way, if you'd like a proof now the error has been explained, look at the residue classes of $n^2$ modulo $3$ that follow from each option for $n$ to prove by contradiction $3|n^2implies 3|n$, so you can write $n=3kimplies n^2=9k^2$.
$endgroup$
– J.G.
Dec 28 '18 at 7:44
1
$begingroup$
@Shaun I agree, we need more of this here. +1
$endgroup$
– Randall
Dec 28 '18 at 13:33