Mixing
For which $m$ does $abequiv -1pmod{m}$ imply $a+bequiv 0pmod{m}$ for positive integers $a$ and $b$?
$begingroup$
This is pretty easy to show for $m=24,$ and I'm pretty sure if $abequiv -1pmod{p^{n}}$ does not imply $a+bequiv 0pmod{p^{n}}$ then $abequiv -1pmod{p^{n+k}}$ doesn't imply $a+bequiv 0pmod{p^{n+k}}$ for any positive integer $k$ either. I haven't managed to find any larger numbers than $24,$ so how would I go about proving there exist no $m>24$? If there do exist $m>24,$ how do I show it (and how do I generate $m$ which satisfy this condition)?
number-theory modular-arithmetic
asked Jan 10 at 2:59
P-addictP-addict
284
$endgroup$
add a comment |
$begingroup$
This is pretty easy to show for $m=24,$ and I'm pretty sure if $abequiv -1pmod{p^{n}}$ does not imply $a+bequiv 0pmod{p^{n}}$ then $abequiv -1pmod{p^{n+k}}$ doesn't imply $a+bequiv 0pmod{p^{n+k}}$ for any positive integer $k$ either. I haven't managed to find any larger numbers than $24,$ so how would I go about proving there exist no $m>24$? If there do exist $m>24,$ how do I show it (and how do I generate $m$ which satisfy this condition)?
number-theory modular-arithmetic
asked Jan 10 at 2:59
P-addictP-addict
284
$endgroup$
$begingroup$
What about the title? It says $a+b equiv 0 mod m$; but the text addresses $a + b equiv -1 mod m$. Both engaging cases. Do you mean one or both?
$endgroup$
– Robert Lewis
Jan 10 at 3:04
1
$begingroup$
So sorry, that was a typo! I meant $a+bequiv 0pmod{m}.$
$endgroup$
– P-addict
Jan 10 at 3:06
$begingroup$
Thanks for the speedy correction!
$endgroup$
– Robert Lewis
Jan 10 at 3:06
$begingroup$
That's equivalent to: $,a,$ invertible $Rightarrow,a^{-1}equiv a [!iff a^2equiv 1] $ Is that what you intend?
$endgroup$
– Bill Dubuque
Jan 10 at 3:12
$begingroup$
Yes, I think that's what I was going for.
$endgroup$
– P-addict
Jan 10 at 3:28
add a comment |
$begingroup$
This is pretty easy to show for $m=24,$ and I'm pretty sure if $abequiv -1pmod{p^{n}}$ does not imply $a+bequiv 0pmod{p^{n}}$ then $abequiv -1pmod{p^{n+k}}$ doesn't imply $a+bequiv 0pmod{p^{n+k}}$ for any positive integer $k$ either. I haven't managed to find any larger numbers than $24,$ so how would I go about proving there exist no $m>24$? If there do exist $m>24,$ how do I show it (and how do I generate $m$ which satisfy this condition)?
number-theory modular-arithmetic
asked Jan 10 at 2:59
P-addictP-addict
284
$endgroup$
This is pretty easy to show for $m=24,$ and I'm pretty sure if $abequiv -1pmod{p^{n}}$ does not imply $a+bequiv 0pmod{p^{n}}$ then $abequiv -1pmod{p^{n+k}}$ doesn't imply $a+bequiv 0pmod{p^{n+k}}$ for any positive integer $k$ either. I haven't managed to find any larger numbers than $24,$ so how would I go about proving there exist no $m>24$? If there do exist $m>24,$ how do I show it (and how do I generate $m$ which satisfy this condition)?
number-theory modular-arithmetic
number-theory modular-arithmetic
asked Jan 10 at 2:59
P-addictP-addict
284
asked Jan 10 at 2:59
P-addictP-addict
284
edited Jan 10 at 3:05
P-addict
asked Jan 10 at 2:59
P-addictP-addict
284
asked Jan 10 at 2:59
P-addictP-addict
284
asked Jan 10 at 2:59
P-addictP-addict
284
284
$begingroup$
What about the title? It says $a+b equiv 0 mod m$; but the text addresses $a + b equiv -1 mod m$. Both engaging cases. Do you mean one or both?
$endgroup$
– Robert Lewis
Jan 10 at 3:04
1
$begingroup$
So sorry, that was a typo! I meant $a+bequiv 0pmod{m}.$
$endgroup$
– P-addict
Jan 10 at 3:06
$begingroup$
Thanks for the speedy correction!
$endgroup$
– Robert Lewis
Jan 10 at 3:06
$begingroup$
That's equivalent to: $,a,$ invertible $Rightarrow,a^{-1}equiv a [!iff a^2equiv 1] $ Is that what you intend?
$endgroup$
– Bill Dubuque
Jan 10 at 3:12
$begingroup$
Yes, I think that's what I was going for.
$endgroup$
– P-addict
Jan 10 at 3:28
add a comment |
$begingroup$
What about the title? It says $a+b equiv 0 mod m$; but the text addresses $a + b equiv -1 mod m$. Both engaging cases. Do you mean one or both?
$endgroup$
– Robert Lewis
Jan 10 at 3:04
1
$begingroup$
So sorry, that was a typo! I meant $a+bequiv 0pmod{m}.$
$endgroup$
– P-addict
Jan 10 at 3:06
$begingroup$
Thanks for the speedy correction!
$endgroup$
– Robert Lewis
Jan 10 at 3:06
$begingroup$
That's equivalent to: $,a,$ invertible $Rightarrow,a^{-1}equiv a [!iff a^2equiv 1] $ Is that what you intend?
$endgroup$
– Bill Dubuque
Jan 10 at 3:12
$begingroup$
Yes, I think that's what I was going for.
$endgroup$
– P-addict
Jan 10 at 3:28
$begingroup$
What about the title? It says $a+b equiv 0 mod m$; but the text addresses $a + b equiv -1 mod m$. Both engaging cases. Do you mean one or both?
$endgroup$
– Robert Lewis
Jan 10 at 3:04
$begingroup$
What about the title? It says $a+b equiv 0 mod m$; but the text addresses $a + b equiv -1 mod m$. Both engaging cases. Do you mean one or both?
$endgroup$
– Robert Lewis
Jan 10 at 3:04
1
1
$begingroup$
So sorry, that was a typo! I meant $a+bequiv 0pmod{m}.$
$endgroup$
– P-addict
Jan 10 at 3:06
$begingroup$
So sorry, that was a typo! I meant $a+bequiv 0pmod{m}.$
$endgroup$
– P-addict
Jan 10 at 3:06
$begingroup$
Thanks for the speedy correction!
$endgroup$
– Robert Lewis
Jan 10 at 3:06
$begingroup$
Thanks for the speedy correction!
$endgroup$
– Robert Lewis
Jan 10 at 3:06
$begingroup$
That's equivalent to: $,a,$ invertible $Rightarrow,a^{-1}equiv a [!iff a^2equiv 1] $ Is that what you intend?
$endgroup$
– Bill Dubuque
Jan 10 at 3:12
$begingroup$
That's equivalent to: $,a,$ invertible $Rightarrow,a^{-1}equiv a [!iff a^2equiv 1] $ Is that what you intend?
$endgroup$
– Bill Dubuque
Jan 10 at 3:12
$begingroup$
Yes, I think that's what I was going for.
$endgroup$
– P-addict
Jan 10 at 3:28
$begingroup$
Yes, I think that's what I was going for.
$endgroup$
– P-addict
Jan 10 at 3:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose that both conditions hold. Then $aequiv -b pmod{m}$ and thus $$a^2 equiv -ab equiv 1 pmod{m},$$
and so $a^2 - 1 = mx.$ So, it suffices for there to be a number which is not its own inverse. For this, the Chinese Remainder Theorem is of great use.
It's clear that, for any prime besides $2, 3,$ there is some number which is not its own inverse (just note that if $a^2 - 1 = px,$ then $(a-1)(a+1) = px,$ and so either $aequiv 1pmod{p}$ or $aequiv -1pmod{p}.$)
So, suppose that some prime $p > 3$ divides $m,$ and that $p^n$ is largest power of $p$ that divides $m.$ Then, find a residue mod $m$ which is congruent to $2$ mod $p^n$ but $1$ modulo every other prime power dividing $m.$ This residue will be invertible as it is relatively prime to $m$, and thus have a unique inverse mod $m.$ But it clearly cannot be its own inverse, as it is congruent to $2$ mod $p^n$ but $2$ is not its own inverse mod $p^n$ since $p > 3,$ and thus the equation $a+b equiv 0 pmod{m}$ does not hold, as if it did the above computations would show that $a$ was its own inverse.
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
$endgroup$
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
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%2f3068176%2ffor-which-m-does-ab-equiv-1-pmodm-imply-ab-equiv-0-pmodm-for-positiv%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$
Suppose that both conditions hold. Then $aequiv -b pmod{m}$ and thus $$a^2 equiv -ab equiv 1 pmod{m},$$
and so $a^2 - 1 = mx.$ So, it suffices for there to be a number which is not its own inverse. For this, the Chinese Remainder Theorem is of great use.
It's clear that, for any prime besides $2, 3,$ there is some number which is not its own inverse (just note that if $a^2 - 1 = px,$ then $(a-1)(a+1) = px,$ and so either $aequiv 1pmod{p}$ or $aequiv -1pmod{p}.$)
So, suppose that some prime $p > 3$ divides $m,$ and that $p^n$ is largest power of $p$ that divides $m.$ Then, find a residue mod $m$ which is congruent to $2$ mod $p^n$ but $1$ modulo every other prime power dividing $m.$ This residue will be invertible as it is relatively prime to $m$, and thus have a unique inverse mod $m.$ But it clearly cannot be its own inverse, as it is congruent to $2$ mod $p^n$ but $2$ is not its own inverse mod $p^n$ since $p > 3,$ and thus the equation $a+b equiv 0 pmod{m}$ does not hold, as if it did the above computations would show that $a$ was its own inverse.
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
$endgroup$
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
add a comment |
$begingroup$
Suppose that both conditions hold. Then $aequiv -b pmod{m}$ and thus $$a^2 equiv -ab equiv 1 pmod{m},$$
and so $a^2 - 1 = mx.$ So, it suffices for there to be a number which is not its own inverse. For this, the Chinese Remainder Theorem is of great use.
It's clear that, for any prime besides $2, 3,$ there is some number which is not its own inverse (just note that if $a^2 - 1 = px,$ then $(a-1)(a+1) = px,$ and so either $aequiv 1pmod{p}$ or $aequiv -1pmod{p}.$)
So, suppose that some prime $p > 3$ divides $m,$ and that $p^n$ is largest power of $p$ that divides $m.$ Then, find a residue mod $m$ which is congruent to $2$ mod $p^n$ but $1$ modulo every other prime power dividing $m.$ This residue will be invertible as it is relatively prime to $m$, and thus have a unique inverse mod $m.$ But it clearly cannot be its own inverse, as it is congruent to $2$ mod $p^n$ but $2$ is not its own inverse mod $p^n$ since $p > 3,$ and thus the equation $a+b equiv 0 pmod{m}$ does not hold, as if it did the above computations would show that $a$ was its own inverse.
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
$endgroup$
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
add a comment |
$begingroup$
Suppose that both conditions hold. Then $aequiv -b pmod{m}$ and thus $$a^2 equiv -ab equiv 1 pmod{m},$$
and so $a^2 - 1 = mx.$ So, it suffices for there to be a number which is not its own inverse. For this, the Chinese Remainder Theorem is of great use.
It's clear that, for any prime besides $2, 3,$ there is some number which is not its own inverse (just note that if $a^2 - 1 = px,$ then $(a-1)(a+1) = px,$ and so either $aequiv 1pmod{p}$ or $aequiv -1pmod{p}.$)
So, suppose that some prime $p > 3$ divides $m,$ and that $p^n$ is largest power of $p$ that divides $m.$ Then, find a residue mod $m$ which is congruent to $2$ mod $p^n$ but $1$ modulo every other prime power dividing $m.$ This residue will be invertible as it is relatively prime to $m$, and thus have a unique inverse mod $m.$ But it clearly cannot be its own inverse, as it is congruent to $2$ mod $p^n$ but $2$ is not its own inverse mod $p^n$ since $p > 3,$ and thus the equation $a+b equiv 0 pmod{m}$ does not hold, as if it did the above computations would show that $a$ was its own inverse.
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
$endgroup$
Suppose that both conditions hold. Then $aequiv -b pmod{m}$ and thus $$a^2 equiv -ab equiv 1 pmod{m},$$
and so $a^2 - 1 = mx.$ So, it suffices for there to be a number which is not its own inverse. For this, the Chinese Remainder Theorem is of great use.
It's clear that, for any prime besides $2, 3,$ there is some number which is not its own inverse (just note that if $a^2 - 1 = px,$ then $(a-1)(a+1) = px,$ and so either $aequiv 1pmod{p}$ or $aequiv -1pmod{p}.$)
So, suppose that some prime $p > 3$ divides $m,$ and that $p^n$ is largest power of $p$ that divides $m.$ Then, find a residue mod $m$ which is congruent to $2$ mod $p^n$ but $1$ modulo every other prime power dividing $m.$ This residue will be invertible as it is relatively prime to $m$, and thus have a unique inverse mod $m.$ But it clearly cannot be its own inverse, as it is congruent to $2$ mod $p^n$ but $2$ is not its own inverse mod $p^n$ since $p > 3,$ and thus the equation $a+b equiv 0 pmod{m}$ does not hold, as if it did the above computations would show that $a$ was its own inverse.
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
answered Jan 10 at 3:19
Michael BarzMichael Barz
915
915
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
add a comment |
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
You haven't specifically answered the question, i.e. "For which $m$...."
$endgroup$
– Bill Dubuque
Jan 10 at 4:05
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
@BillDubuque I have--those m such that no prime $p > 3$ divides $m.$
$endgroup$
– Michael Barz
Jan 10 at 23:34
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
$begingroup$
That's not correct, e.g. $,3^{large 2}!notequiv 1pmod{!16}, 2^{large 2}!notequiv 1pmod{!9} $
$endgroup$
– Bill Dubuque
Jan 10 at 23:40
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%2f3068176%2ffor-which-m-does-ab-equiv-1-pmodm-imply-ab-equiv-0-pmodm-for-positiv%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$
What about the title? It says $a+b equiv 0 mod m$; but the text addresses $a + b equiv -1 mod m$. Both engaging cases. Do you mean one or both?
$endgroup$
– Robert Lewis
Jan 10 at 3:04
1
$begingroup$
So sorry, that was a typo! I meant $a+bequiv 0pmod{m}.$
$endgroup$
– P-addict
Jan 10 at 3:06
$begingroup$
Thanks for the speedy correction!
$endgroup$
– Robert Lewis
Jan 10 at 3:06
$begingroup$
That's equivalent to: $,a,$ invertible $Rightarrow,a^{-1}equiv a [!iff a^2equiv 1] $ Is that what you intend?
$endgroup$
– Bill Dubuque
Jan 10 at 3:12
$begingroup$
Yes, I think that's what I was going for.
$endgroup$
– P-addict
Jan 10 at 3:28