Elementary Number Theory Divisibility Question
$begingroup$
Let $a, b, c in mathbb Z$. I know that if $c|a$ and $c|b$, then $c|a pm b$. I was working on some elementary number theory and I began to wonder if the following were true:$$text{if }c|a text{ and } c|a+b text{, then } c|b$$
I managed a very simple proof:
Suppose $c|a$ and $c|a+b$. It follows that $a=c cdot d$ and $a+b=c cdot d'$, where $d, d' in mathbb Z$. Note that if $a=c cdot d$, then $c cdot d +b=c cdot d'$. Hence $b=c cdot d' -c cdot d$, or $b=c(d-d')$. Letting $d''=d-d' in mathbb Z$, we have $b=c cdot d''$, or $c|b$, as desired.
However, while trying to prove this the good ol' fashioned way (using propositional logic), I'm hitting a barrier that has me second-guessing if my above proof is correct or not. For the life of me, I cannot fathom how $$(P land Q) Rightarrow R equiv (P land R) Rightarrow Q$$
for $P:=c|a$, $Q:=c|b$ and $R:=c|a+b$.
Sorry for the silly question. My propositional logic is a little rusty and I'm probably just overlooking something. Any insight would be greatly appreciated!
elementary-number-theory divisibility propositional-calculus
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
$endgroup$
add a comment |
$begingroup$
Let $a, b, c in mathbb Z$. I know that if $c|a$ and $c|b$, then $c|a pm b$. I was working on some elementary number theory and I began to wonder if the following were true:$$text{if }c|a text{ and } c|a+b text{, then } c|b$$
I managed a very simple proof:
Suppose $c|a$ and $c|a+b$. It follows that $a=c cdot d$ and $a+b=c cdot d'$, where $d, d' in mathbb Z$. Note that if $a=c cdot d$, then $c cdot d +b=c cdot d'$. Hence $b=c cdot d' -c cdot d$, or $b=c(d-d')$. Letting $d''=d-d' in mathbb Z$, we have $b=c cdot d''$, or $c|b$, as desired.
However, while trying to prove this the good ol' fashioned way (using propositional logic), I'm hitting a barrier that has me second-guessing if my above proof is correct or not. For the life of me, I cannot fathom how $$(P land Q) Rightarrow R equiv (P land R) Rightarrow Q$$
for $P:=c|a$, $Q:=c|b$ and $R:=c|a+b$.
Sorry for the silly question. My propositional logic is a little rusty and I'm probably just overlooking something. Any insight would be greatly appreciated!
elementary-number-theory divisibility propositional-calculus
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
$endgroup$
3
$begingroup$
You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(Pwedge Q)Rightarrow R$ is not equivalent to the proposition $(Pwedge R)Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case.
$endgroup$
– Arturo Magidin
Jan 14 at 23:14
2
$begingroup$
So the question is not about elementary number theory. Of course, $cmid a$ and $cmid a+b$ imply $cmid b$. Your proof is correct.
$endgroup$
– Dietrich Burde
Jan 14 at 23:14
2
$begingroup$
Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know.
$endgroup$
– Mark
Jan 14 at 23:16
$begingroup$
Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:23
add a comment |
$begingroup$
Let $a, b, c in mathbb Z$. I know that if $c|a$ and $c|b$, then $c|a pm b$. I was working on some elementary number theory and I began to wonder if the following were true:$$text{if }c|a text{ and } c|a+b text{, then } c|b$$
I managed a very simple proof:
Suppose $c|a$ and $c|a+b$. It follows that $a=c cdot d$ and $a+b=c cdot d'$, where $d, d' in mathbb Z$. Note that if $a=c cdot d$, then $c cdot d +b=c cdot d'$. Hence $b=c cdot d' -c cdot d$, or $b=c(d-d')$. Letting $d''=d-d' in mathbb Z$, we have $b=c cdot d''$, or $c|b$, as desired.
However, while trying to prove this the good ol' fashioned way (using propositional logic), I'm hitting a barrier that has me second-guessing if my above proof is correct or not. For the life of me, I cannot fathom how $$(P land Q) Rightarrow R equiv (P land R) Rightarrow Q$$
for $P:=c|a$, $Q:=c|b$ and $R:=c|a+b$.
Sorry for the silly question. My propositional logic is a little rusty and I'm probably just overlooking something. Any insight would be greatly appreciated!
elementary-number-theory divisibility propositional-calculus
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
$endgroup$
Let $a, b, c in mathbb Z$. I know that if $c|a$ and $c|b$, then $c|a pm b$. I was working on some elementary number theory and I began to wonder if the following were true:$$text{if }c|a text{ and } c|a+b text{, then } c|b$$
I managed a very simple proof:
Suppose $c|a$ and $c|a+b$. It follows that $a=c cdot d$ and $a+b=c cdot d'$, where $d, d' in mathbb Z$. Note that if $a=c cdot d$, then $c cdot d +b=c cdot d'$. Hence $b=c cdot d' -c cdot d$, or $b=c(d-d')$. Letting $d''=d-d' in mathbb Z$, we have $b=c cdot d''$, or $c|b$, as desired.
However, while trying to prove this the good ol' fashioned way (using propositional logic), I'm hitting a barrier that has me second-guessing if my above proof is correct or not. For the life of me, I cannot fathom how $$(P land Q) Rightarrow R equiv (P land R) Rightarrow Q$$
for $P:=c|a$, $Q:=c|b$ and $R:=c|a+b$.
Sorry for the silly question. My propositional logic is a little rusty and I'm probably just overlooking something. Any insight would be greatly appreciated!
elementary-number-theory divisibility propositional-calculus
elementary-number-theory divisibility propositional-calculus
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
asked Jan 14 at 23:09
greycatbirdgreycatbird
1327
1327
3
$begingroup$
You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(Pwedge Q)Rightarrow R$ is not equivalent to the proposition $(Pwedge R)Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case.
$endgroup$
– Arturo Magidin
Jan 14 at 23:14
2
$begingroup$
So the question is not about elementary number theory. Of course, $cmid a$ and $cmid a+b$ imply $cmid b$. Your proof is correct.
$endgroup$
– Dietrich Burde
Jan 14 at 23:14
2
$begingroup$
Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know.
$endgroup$
– Mark
Jan 14 at 23:16
$begingroup$
Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:23
add a comment |
3
$begingroup$
You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(Pwedge Q)Rightarrow R$ is not equivalent to the proposition $(Pwedge R)Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case.
$endgroup$
– Arturo Magidin
Jan 14 at 23:14
2
$begingroup$
So the question is not about elementary number theory. Of course, $cmid a$ and $cmid a+b$ imply $cmid b$. Your proof is correct.
$endgroup$
– Dietrich Burde
Jan 14 at 23:14
2
$begingroup$
Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know.
$endgroup$
– Mark
Jan 14 at 23:16
$begingroup$
Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:23
3
3
$begingroup$
You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(Pwedge Q)Rightarrow R$ is not equivalent to the proposition $(Pwedge R)Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case.
$endgroup$
– Arturo Magidin
Jan 14 at 23:14
$begingroup$
You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(Pwedge Q)Rightarrow R$ is not equivalent to the proposition $(Pwedge R)Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case.
$endgroup$
– Arturo Magidin
Jan 14 at 23:14
2
2
$begingroup$
So the question is not about elementary number theory. Of course, $cmid a$ and $cmid a+b$ imply $cmid b$. Your proof is correct.
$endgroup$
– Dietrich Burde
Jan 14 at 23:14
$begingroup$
So the question is not about elementary number theory. Of course, $cmid a$ and $cmid a+b$ imply $cmid b$. Your proof is correct.
$endgroup$
– Dietrich Burde
Jan 14 at 23:14
2
2
$begingroup$
Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know.
$endgroup$
– Mark
Jan 14 at 23:16
$begingroup$
Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know.
$endgroup$
– Mark
Jan 14 at 23:16
$begingroup$
Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:23
$begingroup$
Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:23
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your number theory proof is correct, but your proposed equivalence in propositioal logic is (in general) not correct, so you can't use it to proof what you want just with your initial knowledge and "propositional magic", you need actual number theory for that.
To see that the propositional formula is generally incorrect, set for example
$$P:=2|x, Q:=4|x, R=2|x$$
Of course, I may have misunderstood what you wanted to achieve with your propositional formula. If that's true, please explain.
answered Jan 14 at 23:22
IngixIngix
5,377259
$endgroup$
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
add a comment |
Your Answer
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%2f3073879%2felementary-number-theory-divisibility-question%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your number theory proof is correct, but your proposed equivalence in propositioal logic is (in general) not correct, so you can't use it to proof what you want just with your initial knowledge and "propositional magic", you need actual number theory for that.
To see that the propositional formula is generally incorrect, set for example
$$P:=2|x, Q:=4|x, R=2|x$$
Of course, I may have misunderstood what you wanted to achieve with your propositional formula. If that's true, please explain.
answered Jan 14 at 23:22
IngixIngix
5,377259
$endgroup$
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
add a comment |
$begingroup$
Your number theory proof is correct, but your proposed equivalence in propositioal logic is (in general) not correct, so you can't use it to proof what you want just with your initial knowledge and "propositional magic", you need actual number theory for that.
To see that the propositional formula is generally incorrect, set for example
$$P:=2|x, Q:=4|x, R=2|x$$
Of course, I may have misunderstood what you wanted to achieve with your propositional formula. If that's true, please explain.
answered Jan 14 at 23:22
IngixIngix
5,377259
$endgroup$
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
add a comment |
$begingroup$
Your number theory proof is correct, but your proposed equivalence in propositioal logic is (in general) not correct, so you can't use it to proof what you want just with your initial knowledge and "propositional magic", you need actual number theory for that.
To see that the propositional formula is generally incorrect, set for example
$$P:=2|x, Q:=4|x, R=2|x$$
Of course, I may have misunderstood what you wanted to achieve with your propositional formula. If that's true, please explain.
answered Jan 14 at 23:22
IngixIngix
5,377259
$endgroup$
Your number theory proof is correct, but your proposed equivalence in propositioal logic is (in general) not correct, so you can't use it to proof what you want just with your initial knowledge and "propositional magic", you need actual number theory for that.
To see that the propositional formula is generally incorrect, set for example
$$P:=2|x, Q:=4|x, R=2|x$$
Of course, I may have misunderstood what you wanted to achieve with your propositional formula. If that's true, please explain.
answered Jan 14 at 23:22
IngixIngix
5,377259
answered Jan 14 at 23:22
IngixIngix
5,377259
answered Jan 14 at 23:22
IngixIngix
5,377259
answered Jan 14 at 23:22
IngixIngix
5,377259
5,377259
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
add a comment |
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
$begingroup$
Thank you for the answer. I was intimidated by the simplicity of the proof. 'If it's too good to be true, it probably is.' I will remember to brush up on my propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:27
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%2f3073879%2felementary-number-theory-divisibility-question%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
3
$begingroup$
You can't prove this from propositional logic alone, because the proof requires the semantics of what you are trying to prove (the meaning of the statements). This is not a tautology. The proposition $(Pwedge Q)Rightarrow R$ is not equivalent to the proposition $(Pwedge R)Rightarrow Q$. The former is true when $P$ and $R$ are true and $Q$ false, but the latter is false in that case.
$endgroup$
– Arturo Magidin
Jan 14 at 23:14
2
$begingroup$
So the question is not about elementary number theory. Of course, $cmid a$ and $cmid a+b$ imply $cmid b$. Your proof is correct.
$endgroup$
– Dietrich Burde
Jan 14 at 23:14
2
$begingroup$
Your proof is correct, but it is really much better to avoid writing so many letters if possible. You could simply write $b=(a+b)-a$ and use the part which as you wrote in the beginning you already know.
$endgroup$
– Mark
Jan 14 at 23:16
$begingroup$
Thank you guys for the response. The proof 'felt' correct, but it seemed strange to me that I've never come across that property before (simple although it may be). That's why I decided to delve deeper using propositional logic.
$endgroup$
– greycatbird
Jan 14 at 23:23