Consider $m$ to be odd and prime. And $A = {0, 1, 2, …, 2m-1}$ is the set of all remainders modulo $2m$.
$begingroup$
Consider $m$ to be odd and prime. And $A = {0, 1, 2, ..., 2m-1}$ is the set of all remainders modulo $2m$. How many elements $x$ in $A$ satisfy $x^2 equiv 1 mod{2m}$?
number-theory prime-numbers modular-arithmetic
asked Oct 20 '18 at 21:37
YFPYFP
3912
$endgroup$
add a comment |
$begingroup$
Consider $m$ to be odd and prime. And $A = {0, 1, 2, ..., 2m-1}$ is the set of all remainders modulo $2m$. How many elements $x$ in $A$ satisfy $x^2 equiv 1 mod{2m}$?
number-theory prime-numbers modular-arithmetic
asked Oct 20 '18 at 21:37
YFPYFP
3912
$endgroup$
$begingroup$
Hint: Chinese remainder theorem
$endgroup$
– Wojowu
Oct 20 '18 at 21:42
$begingroup$
Slight extension of this question 7 hours ago which was $!bmod 2p,$ vs, $,2m $
$endgroup$
– Bill Dubuque
Oct 20 '18 at 21:58
add a comment |
$begingroup$
Consider $m$ to be odd and prime. And $A = {0, 1, 2, ..., 2m-1}$ is the set of all remainders modulo $2m$. How many elements $x$ in $A$ satisfy $x^2 equiv 1 mod{2m}$?
number-theory prime-numbers modular-arithmetic
asked Oct 20 '18 at 21:37
YFPYFP
3912
$endgroup$
Consider $m$ to be odd and prime. And $A = {0, 1, 2, ..., 2m-1}$ is the set of all remainders modulo $2m$. How many elements $x$ in $A$ satisfy $x^2 equiv 1 mod{2m}$?
number-theory prime-numbers modular-arithmetic
number-theory prime-numbers modular-arithmetic
asked Oct 20 '18 at 21:37
YFPYFP
3912
asked Oct 20 '18 at 21:37
YFPYFP
3912
edited Oct 20 '18 at 22:19
YFP
asked Oct 20 '18 at 21:37
YFPYFP
3912
asked Oct 20 '18 at 21:37
YFPYFP
3912
asked Oct 20 '18 at 21:37
YFPYFP
3912
3912
$begingroup$
Hint: Chinese remainder theorem
$endgroup$
– Wojowu
Oct 20 '18 at 21:42
$begingroup$
Slight extension of this question 7 hours ago which was $!bmod 2p,$ vs, $,2m $
$endgroup$
– Bill Dubuque
Oct 20 '18 at 21:58
add a comment |
$begingroup$
Hint: Chinese remainder theorem
$endgroup$
– Wojowu
Oct 20 '18 at 21:42
$begingroup$
Slight extension of this question 7 hours ago which was $!bmod 2p,$ vs, $,2m $
$endgroup$
– Bill Dubuque
Oct 20 '18 at 21:58
$begingroup$
Hint: Chinese remainder theorem
$endgroup$
– Wojowu
Oct 20 '18 at 21:42
$begingroup$
Hint: Chinese remainder theorem
$endgroup$
– Wojowu
Oct 20 '18 at 21:42
$begingroup$
Slight extension of this question 7 hours ago which was $!bmod 2p,$ vs, $,2m $
$endgroup$
– Bill Dubuque
Oct 20 '18 at 21:58
$begingroup$
Slight extension of this question 7 hours ago which was $!bmod 2p,$ vs, $,2m $
$endgroup$
– Bill Dubuque
Oct 20 '18 at 21:58
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The solutions to $x^2equiv 1pmod p$ are $xequiv pm1pmod p$, the only solution to $x^2equiv 1pmod 2$ is $xequiv 1pmod 2$. By the Chinese Remainder Theorem, we conclude that the solutions modulo $2p$ and taken from ${0,ldots, 2p-1}$ are $1$ and $2p-1$. Now we have to count the members of these residue classes in ${0,ldots,2m-1}$.
If $m$ is a multiple of $p$, say $m=kp$, we obviously find $2k$ such numbers, namely $2jp+1$ for $0le j<k$ and $2jp-1$ for $1le jle k$.
Otherwise, if $m=kp+r$, $0<k<p$, we have $2jp+1$ for $0le jle k$ and $2jp-1$ for $1le jle k$, so a total of $2k+1$ such numbers.
The general answer is thus
$$ leftlceil frac mprightrceil+leftlfloor frac mprightrfloor. $$
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
$endgroup$
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
add a comment |
$begingroup$
Hint $ $ Apply the following with $ p=m, q = 2 $ and $ b,c = xpm1 $
Lemma $ $ If $,pnmid q,$ are primes and $,color{#c00}{qmid b!-!c},$ then $ pqmid bciff pqmid b,$ or $,pqmid c$
Proof $, pqmid bciff pqmid b,$ or $,pqmid c,$ or $,smash[b]{underbrace{pmid b,,color{#c00}{qmid c}}},$ or $,pmid c,,qmid b $ by unique factorization.
By hypothesis $,color{#c00}{qmid b!iff! qmid c},,$ therefore $,{pmid b,, color{#c00}{qmid c}}iff pmid b,color{#c00}{qmid b}iff pqmid b$
Similarly, the final case is equivalent to $,pqmid c$
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
$endgroup$
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%2f2963799%2fconsider-m-to-be-odd-and-prime-and-a-0-1-2-2m-1-is-the-set-of%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$
The solutions to $x^2equiv 1pmod p$ are $xequiv pm1pmod p$, the only solution to $x^2equiv 1pmod 2$ is $xequiv 1pmod 2$. By the Chinese Remainder Theorem, we conclude that the solutions modulo $2p$ and taken from ${0,ldots, 2p-1}$ are $1$ and $2p-1$. Now we have to count the members of these residue classes in ${0,ldots,2m-1}$.
If $m$ is a multiple of $p$, say $m=kp$, we obviously find $2k$ such numbers, namely $2jp+1$ for $0le j<k$ and $2jp-1$ for $1le jle k$.
Otherwise, if $m=kp+r$, $0<k<p$, we have $2jp+1$ for $0le jle k$ and $2jp-1$ for $1le jle k$, so a total of $2k+1$ such numbers.
The general answer is thus
$$ leftlceil frac mprightrceil+leftlfloor frac mprightrfloor. $$
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
$endgroup$
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
add a comment |
$begingroup$
The solutions to $x^2equiv 1pmod p$ are $xequiv pm1pmod p$, the only solution to $x^2equiv 1pmod 2$ is $xequiv 1pmod 2$. By the Chinese Remainder Theorem, we conclude that the solutions modulo $2p$ and taken from ${0,ldots, 2p-1}$ are $1$ and $2p-1$. Now we have to count the members of these residue classes in ${0,ldots,2m-1}$.
If $m$ is a multiple of $p$, say $m=kp$, we obviously find $2k$ such numbers, namely $2jp+1$ for $0le j<k$ and $2jp-1$ for $1le jle k$.
Otherwise, if $m=kp+r$, $0<k<p$, we have $2jp+1$ for $0le jle k$ and $2jp-1$ for $1le jle k$, so a total of $2k+1$ such numbers.
The general answer is thus
$$ leftlceil frac mprightrceil+leftlfloor frac mprightrfloor. $$
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
$endgroup$
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
add a comment |
$begingroup$
The solutions to $x^2equiv 1pmod p$ are $xequiv pm1pmod p$, the only solution to $x^2equiv 1pmod 2$ is $xequiv 1pmod 2$. By the Chinese Remainder Theorem, we conclude that the solutions modulo $2p$ and taken from ${0,ldots, 2p-1}$ are $1$ and $2p-1$. Now we have to count the members of these residue classes in ${0,ldots,2m-1}$.
If $m$ is a multiple of $p$, say $m=kp$, we obviously find $2k$ such numbers, namely $2jp+1$ for $0le j<k$ and $2jp-1$ for $1le jle k$.
Otherwise, if $m=kp+r$, $0<k<p$, we have $2jp+1$ for $0le jle k$ and $2jp-1$ for $1le jle k$, so a total of $2k+1$ such numbers.
The general answer is thus
$$ leftlceil frac mprightrceil+leftlfloor frac mprightrfloor. $$
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
$endgroup$
The solutions to $x^2equiv 1pmod p$ are $xequiv pm1pmod p$, the only solution to $x^2equiv 1pmod 2$ is $xequiv 1pmod 2$. By the Chinese Remainder Theorem, we conclude that the solutions modulo $2p$ and taken from ${0,ldots, 2p-1}$ are $1$ and $2p-1$. Now we have to count the members of these residue classes in ${0,ldots,2m-1}$.
If $m$ is a multiple of $p$, say $m=kp$, we obviously find $2k$ such numbers, namely $2jp+1$ for $0le j<k$ and $2jp-1$ for $1le jle k$.
Otherwise, if $m=kp+r$, $0<k<p$, we have $2jp+1$ for $0le jle k$ and $2jp-1$ for $1le jle k$, so a total of $2k+1$ such numbers.
The general answer is thus
$$ leftlceil frac mprightrceil+leftlfloor frac mprightrfloor. $$
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
answered Oct 20 '18 at 21:47
Hagen von EitzenHagen von Eitzen
284k23274508
284k23274508
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
add a comment |
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
Can also be solved without CRT.
$endgroup$
– Bill Dubuque
Oct 20 '18 at 22:01
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
$begingroup$
@HagenvonEitzen Sorry I had a type before due to a confusion, just edited the question
$endgroup$
– YFP
Oct 20 '18 at 22:21
add a comment |
$begingroup$
Hint $ $ Apply the following with $ p=m, q = 2 $ and $ b,c = xpm1 $
Lemma $ $ If $,pnmid q,$ are primes and $,color{#c00}{qmid b!-!c},$ then $ pqmid bciff pqmid b,$ or $,pqmid c$
Proof $, pqmid bciff pqmid b,$ or $,pqmid c,$ or $,smash[b]{underbrace{pmid b,,color{#c00}{qmid c}}},$ or $,pmid c,,qmid b $ by unique factorization.
By hypothesis $,color{#c00}{qmid b!iff! qmid c},,$ therefore $,{pmid b,, color{#c00}{qmid c}}iff pmid b,color{#c00}{qmid b}iff pqmid b$
Similarly, the final case is equivalent to $,pqmid c$
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
$endgroup$
add a comment |
$begingroup$
Hint $ $ Apply the following with $ p=m, q = 2 $ and $ b,c = xpm1 $
Lemma $ $ If $,pnmid q,$ are primes and $,color{#c00}{qmid b!-!c},$ then $ pqmid bciff pqmid b,$ or $,pqmid c$
Proof $, pqmid bciff pqmid b,$ or $,pqmid c,$ or $,smash[b]{underbrace{pmid b,,color{#c00}{qmid c}}},$ or $,pmid c,,qmid b $ by unique factorization.
By hypothesis $,color{#c00}{qmid b!iff! qmid c},,$ therefore $,{pmid b,, color{#c00}{qmid c}}iff pmid b,color{#c00}{qmid b}iff pqmid b$
Similarly, the final case is equivalent to $,pqmid c$
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
$endgroup$
add a comment |
$begingroup$
Hint $ $ Apply the following with $ p=m, q = 2 $ and $ b,c = xpm1 $
Lemma $ $ If $,pnmid q,$ are primes and $,color{#c00}{qmid b!-!c},$ then $ pqmid bciff pqmid b,$ or $,pqmid c$
Proof $, pqmid bciff pqmid b,$ or $,pqmid c,$ or $,smash[b]{underbrace{pmid b,,color{#c00}{qmid c}}},$ or $,pmid c,,qmid b $ by unique factorization.
By hypothesis $,color{#c00}{qmid b!iff! qmid c},,$ therefore $,{pmid b,, color{#c00}{qmid c}}iff pmid b,color{#c00}{qmid b}iff pqmid b$
Similarly, the final case is equivalent to $,pqmid c$
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
$endgroup$
Hint $ $ Apply the following with $ p=m, q = 2 $ and $ b,c = xpm1 $
Lemma $ $ If $,pnmid q,$ are primes and $,color{#c00}{qmid b!-!c},$ then $ pqmid bciff pqmid b,$ or $,pqmid c$
Proof $, pqmid bciff pqmid b,$ or $,pqmid c,$ or $,smash[b]{underbrace{pmid b,,color{#c00}{qmid c}}},$ or $,pmid c,,qmid b $ by unique factorization.
By hypothesis $,color{#c00}{qmid b!iff! qmid c},,$ therefore $,{pmid b,, color{#c00}{qmid c}}iff pmid b,color{#c00}{qmid b}iff pqmid b$
Similarly, the final case is equivalent to $,pqmid c$
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
answered Jan 15 at 23:37
Bill DubuqueBill Dubuque
214k29198660
214k29198660
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%2f2963799%2fconsider-m-to-be-odd-and-prime-and-a-0-1-2-2m-1-is-the-set-of%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$
Hint: Chinese remainder theorem
$endgroup$
– Wojowu
Oct 20 '18 at 21:42
$begingroup$
Slight extension of this question 7 hours ago which was $!bmod 2p,$ vs, $,2m $
$endgroup$
– Bill Dubuque
Oct 20 '18 at 21:58