Mixing
If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$
$begingroup$
I have to write a proof for
If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$
The way I solved it is:
Given $m$ is odd this means that $m = 2k + 1$ where $k$ is some integer.
Given $n-1$ is divisible by $3$, this means that $n-1=3L$ or $n= 3L +1$ where $L$ is some integer.
It follows that $(nm) - 1 = (3L +1)(2K +1) = 6KL + 3L + 2k$
This doesn't seem to me to be divisible by $6$. But the online exercise we are using for my class solves $(3L +1)(2K +1)$ to be $6KL + 1$, which doesn't seem like because FOIL. What could I be doing wrong and what is the right answer to this proof?
discrete-mathematics proof-verification proof-explanation
asked Jan 31 at 12:48
SamSam
47418
$endgroup$
add a comment |
$begingroup$
I have to write a proof for
If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$
The way I solved it is:
Given $m$ is odd this means that $m = 2k + 1$ where $k$ is some integer.
Given $n-1$ is divisible by $3$, this means that $n-1=3L$ or $n= 3L +1$ where $L$ is some integer.
It follows that $(nm) - 1 = (3L +1)(2K +1) = 6KL + 3L + 2k$
This doesn't seem to me to be divisible by $6$. But the online exercise we are using for my class solves $(3L +1)(2K +1)$ to be $6KL + 1$, which doesn't seem like because FOIL. What could I be doing wrong and what is the right answer to this proof?
discrete-mathematics proof-verification proof-explanation
asked Jan 31 at 12:48
SamSam
47418
$endgroup$
$begingroup$
$mn-1=(m-1)(n-1)+m-1+n-1equiv m-1+n-1pmod6$
$endgroup$
– lab bhattacharjee
Jan 31 at 12:50
$begingroup$
"that $m=2k+1$ where $k$ is some integer" is not an assumption, it's a given.
$endgroup$
– Henrik
Jan 31 at 12:56
$begingroup$
Counterexample: if $m=3$ then $nm-1 = 2 mod 3 space forall n$ so $nm-1$ is never divisible by $6$ (it's not even divisible by $3$).
$endgroup$
– gandalf61
Jan 31 at 13:43
add a comment |
$begingroup$
I have to write a proof for
If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$
The way I solved it is:
Given $m$ is odd this means that $m = 2k + 1$ where $k$ is some integer.
Given $n-1$ is divisible by $3$, this means that $n-1=3L$ or $n= 3L +1$ where $L$ is some integer.
It follows that $(nm) - 1 = (3L +1)(2K +1) = 6KL + 3L + 2k$
This doesn't seem to me to be divisible by $6$. But the online exercise we are using for my class solves $(3L +1)(2K +1)$ to be $6KL + 1$, which doesn't seem like because FOIL. What could I be doing wrong and what is the right answer to this proof?
discrete-mathematics proof-verification proof-explanation
asked Jan 31 at 12:48
SamSam
47418
$endgroup$
I have to write a proof for
If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$
The way I solved it is:
Given $m$ is odd this means that $m = 2k + 1$ where $k$ is some integer.
Given $n-1$ is divisible by $3$, this means that $n-1=3L$ or $n= 3L +1$ where $L$ is some integer.
It follows that $(nm) - 1 = (3L +1)(2K +1) = 6KL + 3L + 2k$
This doesn't seem to me to be divisible by $6$. But the online exercise we are using for my class solves $(3L +1)(2K +1)$ to be $6KL + 1$, which doesn't seem like because FOIL. What could I be doing wrong and what is the right answer to this proof?
discrete-mathematics proof-verification proof-explanation
discrete-mathematics proof-verification proof-explanation
asked Jan 31 at 12:48
SamSam
47418
asked Jan 31 at 12:48
SamSam
47418
edited Jan 31 at 13:04
Sam
asked Jan 31 at 12:48
SamSam
47418
asked Jan 31 at 12:48
SamSam
47418
asked Jan 31 at 12:48
SamSam
47418
47418
$begingroup$
$mn-1=(m-1)(n-1)+m-1+n-1equiv m-1+n-1pmod6$
$endgroup$
– lab bhattacharjee
Jan 31 at 12:50
$begingroup$
"that $m=2k+1$ where $k$ is some integer" is not an assumption, it's a given.
$endgroup$
– Henrik
Jan 31 at 12:56
$begingroup$
Counterexample: if $m=3$ then $nm-1 = 2 mod 3 space forall n$ so $nm-1$ is never divisible by $6$ (it's not even divisible by $3$).
$endgroup$
– gandalf61
Jan 31 at 13:43
add a comment |
$begingroup$
$mn-1=(m-1)(n-1)+m-1+n-1equiv m-1+n-1pmod6$
$endgroup$
– lab bhattacharjee
Jan 31 at 12:50
$begingroup$
"that $m=2k+1$ where $k$ is some integer" is not an assumption, it's a given.
$endgroup$
– Henrik
Jan 31 at 12:56
$begingroup$
Counterexample: if $m=3$ then $nm-1 = 2 mod 3 space forall n$ so $nm-1$ is never divisible by $6$ (it's not even divisible by $3$).
$endgroup$
– gandalf61
Jan 31 at 13:43
$begingroup$
$mn-1=(m-1)(n-1)+m-1+n-1equiv m-1+n-1pmod6$
$endgroup$
– lab bhattacharjee
Jan 31 at 12:50
$begingroup$
$mn-1=(m-1)(n-1)+m-1+n-1equiv m-1+n-1pmod6$
$endgroup$
– lab bhattacharjee
Jan 31 at 12:50
$begingroup$
"that $m=2k+1$ where $k$ is some integer" is not an assumption, it's a given.
$endgroup$
– Henrik
Jan 31 at 12:56
$begingroup$
"that $m=2k+1$ where $k$ is some integer" is not an assumption, it's a given.
$endgroup$
– Henrik
Jan 31 at 12:56
$begingroup$
Counterexample: if $m=3$ then $nm-1 = 2 mod 3 space forall n$ so $nm-1$ is never divisible by $6$ (it's not even divisible by $3$).
$endgroup$
– gandalf61
Jan 31 at 13:43
$begingroup$
Counterexample: if $m=3$ then $nm-1 = 2 mod 3 space forall n$ so $nm-1$ is never divisible by $6$ (it's not even divisible by $3$).
$endgroup$
– gandalf61
Jan 31 at 13:43
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Given $m = 2k + 1$ and $n = 3l + 1$, we get
$$
mn - 1 = (2k+1)(3l+1) - 1 = 6kl + 2k + 3l + 1 - 1\
= 6kl + 2k + 3l
$$
And if this doesn't look like it's always divisible by $6$, then that's because it isn't. This is best proven by just giving an example. For instance, $k = l = 1$ gives $6 + 2 + 3 = 11$. Translating this back to $m$ and $n$, we get
$$
m = 2k + 1 = 3\
n = 3l+1 = 4
$$
and we can easily check that in this special case
$m$ is odd
$n-1$ is divisible by $3$
$mn - 1$ is not divisible by $6$.
which means we have disproven the statement.
answered Jan 31 at 12:55
ArthurArthur
122k7122211
$endgroup$
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
add a comment |
$begingroup$
The inference holds true $iff m,nequiv 1pmod{!6},,$ by case $,p,q = 2,3,$ below.
Lemma $ $ Suppose that $,m,n,p,q,$ are integers and $ ell = {rm lcm}(p,q) .,$
$$ {rm If} begin{align} mequiv 1!!!pmod{!p}\ nequiv 1!!!pmod{!q}end{align} {rm then} mnequiv 1!!!pmod{!ell} iff m,nequiv 1!!!pmod{!ell}$$
Proof $ (Rightarrow) $ Since $, pmid ell,$ and $,mnequiv 1pmod{ell},$ this congruence persists $!bmod p,$ so
$$bmod p!: color{#c00}{mequiv 1}, color{#c00}mnequiv 1,Rightarrow, nequiv 1$$
Similarly we infer $, mequiv 1pmod{!q}.,$ Hence $,p,qmid m!-!1,n!-!1Rightarrow, {rm lcm}(p,q)mid n!-!1,m!-!1$
$(Leftarrow) bmod ell!:, m,nequiv 1,Rightarrow, mnequiv 1$
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
$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%2f3094847%2fif-m-is-odd-and-n-1-is-divisible-by-3-then-nm-1-is-divisible-by-6%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Given $m = 2k + 1$ and $n = 3l + 1$, we get
$$
mn - 1 = (2k+1)(3l+1) - 1 = 6kl + 2k + 3l + 1 - 1\
= 6kl + 2k + 3l
$$
And if this doesn't look like it's always divisible by $6$, then that's because it isn't. This is best proven by just giving an example. For instance, $k = l = 1$ gives $6 + 2 + 3 = 11$. Translating this back to $m$ and $n$, we get
$$
m = 2k + 1 = 3\
n = 3l+1 = 4
$$
and we can easily check that in this special case
$m$ is odd
$n-1$ is divisible by $3$
$mn - 1$ is not divisible by $6$.
which means we have disproven the statement.
answered Jan 31 at 12:55
ArthurArthur
122k7122211
$endgroup$
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
add a comment |
$begingroup$
Given $m = 2k + 1$ and $n = 3l + 1$, we get
$$
mn - 1 = (2k+1)(3l+1) - 1 = 6kl + 2k + 3l + 1 - 1\
= 6kl + 2k + 3l
$$
And if this doesn't look like it's always divisible by $6$, then that's because it isn't. This is best proven by just giving an example. For instance, $k = l = 1$ gives $6 + 2 + 3 = 11$. Translating this back to $m$ and $n$, we get
$$
m = 2k + 1 = 3\
n = 3l+1 = 4
$$
and we can easily check that in this special case
$m$ is odd
$n-1$ is divisible by $3$
$mn - 1$ is not divisible by $6$.
which means we have disproven the statement.
answered Jan 31 at 12:55
ArthurArthur
122k7122211
$endgroup$
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
add a comment |
$begingroup$
Given $m = 2k + 1$ and $n = 3l + 1$, we get
$$
mn - 1 = (2k+1)(3l+1) - 1 = 6kl + 2k + 3l + 1 - 1\
= 6kl + 2k + 3l
$$
And if this doesn't look like it's always divisible by $6$, then that's because it isn't. This is best proven by just giving an example. For instance, $k = l = 1$ gives $6 + 2 + 3 = 11$. Translating this back to $m$ and $n$, we get
$$
m = 2k + 1 = 3\
n = 3l+1 = 4
$$
and we can easily check that in this special case
$m$ is odd
$n-1$ is divisible by $3$
$mn - 1$ is not divisible by $6$.
which means we have disproven the statement.
answered Jan 31 at 12:55
ArthurArthur
122k7122211
$endgroup$
Given $m = 2k + 1$ and $n = 3l + 1$, we get
$$
mn - 1 = (2k+1)(3l+1) - 1 = 6kl + 2k + 3l + 1 - 1\
= 6kl + 2k + 3l
$$
And if this doesn't look like it's always divisible by $6$, then that's because it isn't. This is best proven by just giving an example. For instance, $k = l = 1$ gives $6 + 2 + 3 = 11$. Translating this back to $m$ and $n$, we get
$$
m = 2k + 1 = 3\
n = 3l+1 = 4
$$
and we can easily check that in this special case
$m$ is odd
$n-1$ is divisible by $3$
$mn - 1$ is not divisible by $6$.
which means we have disproven the statement.
answered Jan 31 at 12:55
ArthurArthur
122k7122211
answered Jan 31 at 12:55
ArthurArthur
122k7122211
answered Jan 31 at 12:55
ArthurArthur
122k7122211
answered Jan 31 at 12:55
ArthurArthur
122k7122211
122k7122211
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
add a comment |
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
$begingroup$
In fact we can easily determine precisely when it holds true - see my answer.
$endgroup$
– Bill Dubuque
Jan 31 at 16:55
add a comment |
$begingroup$
The inference holds true $iff m,nequiv 1pmod{!6},,$ by case $,p,q = 2,3,$ below.
Lemma $ $ Suppose that $,m,n,p,q,$ are integers and $ ell = {rm lcm}(p,q) .,$
$$ {rm If} begin{align} mequiv 1!!!pmod{!p}\ nequiv 1!!!pmod{!q}end{align} {rm then} mnequiv 1!!!pmod{!ell} iff m,nequiv 1!!!pmod{!ell}$$
Proof $ (Rightarrow) $ Since $, pmid ell,$ and $,mnequiv 1pmod{ell},$ this congruence persists $!bmod p,$ so
$$bmod p!: color{#c00}{mequiv 1}, color{#c00}mnequiv 1,Rightarrow, nequiv 1$$
Similarly we infer $, mequiv 1pmod{!q}.,$ Hence $,p,qmid m!-!1,n!-!1Rightarrow, {rm lcm}(p,q)mid n!-!1,m!-!1$
$(Leftarrow) bmod ell!:, m,nequiv 1,Rightarrow, mnequiv 1$
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
add a comment |
$begingroup$
The inference holds true $iff m,nequiv 1pmod{!6},,$ by case $,p,q = 2,3,$ below.
Lemma $ $ Suppose that $,m,n,p,q,$ are integers and $ ell = {rm lcm}(p,q) .,$
$$ {rm If} begin{align} mequiv 1!!!pmod{!p}\ nequiv 1!!!pmod{!q}end{align} {rm then} mnequiv 1!!!pmod{!ell} iff m,nequiv 1!!!pmod{!ell}$$
Proof $ (Rightarrow) $ Since $, pmid ell,$ and $,mnequiv 1pmod{ell},$ this congruence persists $!bmod p,$ so
$$bmod p!: color{#c00}{mequiv 1}, color{#c00}mnequiv 1,Rightarrow, nequiv 1$$
Similarly we infer $, mequiv 1pmod{!q}.,$ Hence $,p,qmid m!-!1,n!-!1Rightarrow, {rm lcm}(p,q)mid n!-!1,m!-!1$
$(Leftarrow) bmod ell!:, m,nequiv 1,Rightarrow, mnequiv 1$
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
add a comment |
$begingroup$
The inference holds true $iff m,nequiv 1pmod{!6},,$ by case $,p,q = 2,3,$ below.
Lemma $ $ Suppose that $,m,n,p,q,$ are integers and $ ell = {rm lcm}(p,q) .,$
$$ {rm If} begin{align} mequiv 1!!!pmod{!p}\ nequiv 1!!!pmod{!q}end{align} {rm then} mnequiv 1!!!pmod{!ell} iff m,nequiv 1!!!pmod{!ell}$$
Proof $ (Rightarrow) $ Since $, pmid ell,$ and $,mnequiv 1pmod{ell},$ this congruence persists $!bmod p,$ so
$$bmod p!: color{#c00}{mequiv 1}, color{#c00}mnequiv 1,Rightarrow, nequiv 1$$
Similarly we infer $, mequiv 1pmod{!q}.,$ Hence $,p,qmid m!-!1,n!-!1Rightarrow, {rm lcm}(p,q)mid n!-!1,m!-!1$
$(Leftarrow) bmod ell!:, m,nequiv 1,Rightarrow, mnequiv 1$
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
$endgroup$
The inference holds true $iff m,nequiv 1pmod{!6},,$ by case $,p,q = 2,3,$ below.
Lemma $ $ Suppose that $,m,n,p,q,$ are integers and $ ell = {rm lcm}(p,q) .,$
$$ {rm If} begin{align} mequiv 1!!!pmod{!p}\ nequiv 1!!!pmod{!q}end{align} {rm then} mnequiv 1!!!pmod{!ell} iff m,nequiv 1!!!pmod{!ell}$$
Proof $ (Rightarrow) $ Since $, pmid ell,$ and $,mnequiv 1pmod{ell},$ this congruence persists $!bmod p,$ so
$$bmod p!: color{#c00}{mequiv 1}, color{#c00}mnequiv 1,Rightarrow, nequiv 1$$
Similarly we infer $, mequiv 1pmod{!q}.,$ Hence $,p,qmid m!-!1,n!-!1Rightarrow, {rm lcm}(p,q)mid n!-!1,m!-!1$
$(Leftarrow) bmod ell!:, m,nequiv 1,Rightarrow, mnequiv 1$
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
edited Jan 31 at 19:24
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
answered Jan 31 at 16:54
Bill DubuqueBill Dubuque
213k29196654
213k29196654
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%2f3094847%2fif-m-is-odd-and-n-1-is-divisible-by-3-then-nm-1-is-divisible-by-6%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$
$mn-1=(m-1)(n-1)+m-1+n-1equiv m-1+n-1pmod6$
$endgroup$
– lab bhattacharjee
Jan 31 at 12:50
$begingroup$
"that $m=2k+1$ where $k$ is some integer" is not an assumption, it's a given.
$endgroup$
– Henrik
Jan 31 at 12:56
$begingroup$
Counterexample: if $m=3$ then $nm-1 = 2 mod 3 space forall n$ so $nm-1$ is never divisible by $6$ (it's not even divisible by $3$).
$endgroup$
– gandalf61
Jan 31 at 13:43