Does the order of $2$ in $Z_p$ divide the order of $2$ in $Z_n$?
$begingroup$
Givens. Consider $(Z_n, times)$ the group of integers coprime with $n = pq$, where $p, q$ are prime numbers. Similarly, $(Z_p, times)$ is the group of integers ${0, 1, 2, ..., p - 1}$ coprime with $p$.
Question. Is it true that $o(2, p)$ divides $o(2, n)$, where $o(i, y)$ describes the order of $i$ in $(Z_y, times)$? Why?
Remarks. I know the size of the group $Z_n$ is $varphi(n) = (p -1)(q - 1)$, the Euler totient function. I also know that $o(2, p) = p$ because $p$ is prime and every group of prime order is cyclic and any member of it is a generator --- I can prove that. But I don't really see if these facts I have are relevant to the question.
group-theory number-theory elementary-number-theory finite-groups algebraic-number-theory
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
$endgroup$
add a comment |
$begingroup$
Givens. Consider $(Z_n, times)$ the group of integers coprime with $n = pq$, where $p, q$ are prime numbers. Similarly, $(Z_p, times)$ is the group of integers ${0, 1, 2, ..., p - 1}$ coprime with $p$.
Question. Is it true that $o(2, p)$ divides $o(2, n)$, where $o(i, y)$ describes the order of $i$ in $(Z_y, times)$? Why?
Remarks. I know the size of the group $Z_n$ is $varphi(n) = (p -1)(q - 1)$, the Euler totient function. I also know that $o(2, p) = p$ because $p$ is prime and every group of prime order is cyclic and any member of it is a generator --- I can prove that. But I don't really see if these facts I have are relevant to the question.
group-theory number-theory elementary-number-theory finite-groups algebraic-number-theory
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
$endgroup$
add a comment |
$begingroup$
Givens. Consider $(Z_n, times)$ the group of integers coprime with $n = pq$, where $p, q$ are prime numbers. Similarly, $(Z_p, times)$ is the group of integers ${0, 1, 2, ..., p - 1}$ coprime with $p$.
Question. Is it true that $o(2, p)$ divides $o(2, n)$, where $o(i, y)$ describes the order of $i$ in $(Z_y, times)$? Why?
Remarks. I know the size of the group $Z_n$ is $varphi(n) = (p -1)(q - 1)$, the Euler totient function. I also know that $o(2, p) = p$ because $p$ is prime and every group of prime order is cyclic and any member of it is a generator --- I can prove that. But I don't really see if these facts I have are relevant to the question.
group-theory number-theory elementary-number-theory finite-groups algebraic-number-theory
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
$endgroup$
Givens. Consider $(Z_n, times)$ the group of integers coprime with $n = pq$, where $p, q$ are prime numbers. Similarly, $(Z_p, times)$ is the group of integers ${0, 1, 2, ..., p - 1}$ coprime with $p$.
Question. Is it true that $o(2, p)$ divides $o(2, n)$, where $o(i, y)$ describes the order of $i$ in $(Z_y, times)$? Why?
Remarks. I know the size of the group $Z_n$ is $varphi(n) = (p -1)(q - 1)$, the Euler totient function. I also know that $o(2, p) = p$ because $p$ is prime and every group of prime order is cyclic and any member of it is a generator --- I can prove that. But I don't really see if these facts I have are relevant to the question.
group-theory number-theory elementary-number-theory finite-groups algebraic-number-theory
group-theory number-theory elementary-number-theory finite-groups algebraic-number-theory
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
asked Jan 22 at 23:06
Joep AwinitaJoep Awinita
807
807
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
If $2^kequiv 1mod{n}$, then also $2^kequiv 1mod{p}$, so that $k$ is a multiple of $o(2,p)$.
This applies in general: if $mmid n$, then $o(i,m)mid o(i,n)$ (as long as $i$ is prime to both $m$ and $n$).
answered Jan 22 at 23:57
rogerlrogerl
18k22747
$endgroup$
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
add a comment |
$begingroup$
Yes. In fact we can establish something more general. Let $r$ be any positive integer and let $p_1,ldots, p_r$ be any $r$ primes. Next let $a$ an integer. Suppose $a^l equiv 1$ $mod p_1p_2ldots p_r$ (and note that $a$ does not have to be 2). Then $a^l = 1 + m(p_1 ldots p_r)$ $=1 +(mp_2p_3 ldots)p_1$ which implies that $a^l equiv 1$ mod $p_1$.
answered Jan 23 at 0:06
MikeMike
4,256412
$endgroup$
add a comment |
$begingroup$
Yes. More generally:
If $phi: G to G'$ is a group homomorphism and $g in G$ has finite order, then $o(phi(g))$ divides $o(g)$.
See a proof here.
This general fact applies to your case because $x bmod n mapsto x bmod d$ defines a group homomorphism $mathbb Z_n^times to mathbb Z_d^times$ if $d$ divides $n$.
answered Jan 23 at 0:17
lhflhf
166k10171396
$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%2f3083843%2fdoes-the-order-of-2-in-z-p-divide-the-order-of-2-in-z-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If $2^kequiv 1mod{n}$, then also $2^kequiv 1mod{p}$, so that $k$ is a multiple of $o(2,p)$.
This applies in general: if $mmid n$, then $o(i,m)mid o(i,n)$ (as long as $i$ is prime to both $m$ and $n$).
answered Jan 22 at 23:57
rogerlrogerl
18k22747
$endgroup$
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
add a comment |
$begingroup$
If $2^kequiv 1mod{n}$, then also $2^kequiv 1mod{p}$, so that $k$ is a multiple of $o(2,p)$.
This applies in general: if $mmid n$, then $o(i,m)mid o(i,n)$ (as long as $i$ is prime to both $m$ and $n$).
answered Jan 22 at 23:57
rogerlrogerl
18k22747
$endgroup$
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
add a comment |
$begingroup$
If $2^kequiv 1mod{n}$, then also $2^kequiv 1mod{p}$, so that $k$ is a multiple of $o(2,p)$.
This applies in general: if $mmid n$, then $o(i,m)mid o(i,n)$ (as long as $i$ is prime to both $m$ and $n$).
answered Jan 22 at 23:57
rogerlrogerl
18k22747
$endgroup$
If $2^kequiv 1mod{n}$, then also $2^kequiv 1mod{p}$, so that $k$ is a multiple of $o(2,p)$.
This applies in general: if $mmid n$, then $o(i,m)mid o(i,n)$ (as long as $i$ is prime to both $m$ and $n$).
answered Jan 22 at 23:57
rogerlrogerl
18k22747
edited Jan 23 at 0:03
answered Jan 22 at 23:57
rogerlrogerl
18k22747
answered Jan 22 at 23:57
rogerlrogerl
18k22747
answered Jan 22 at 23:57
rogerlrogerl
18k22747
18k22747
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
add a comment |
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
You mean $2^k equiv 1$?
$endgroup$
– Mike
Jan 23 at 0:00
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
$begingroup$
@Mike Thanks, fixed.
$endgroup$
– rogerl
Jan 23 at 0:04
add a comment |
$begingroup$
Yes. In fact we can establish something more general. Let $r$ be any positive integer and let $p_1,ldots, p_r$ be any $r$ primes. Next let $a$ an integer. Suppose $a^l equiv 1$ $mod p_1p_2ldots p_r$ (and note that $a$ does not have to be 2). Then $a^l = 1 + m(p_1 ldots p_r)$ $=1 +(mp_2p_3 ldots)p_1$ which implies that $a^l equiv 1$ mod $p_1$.
answered Jan 23 at 0:06
MikeMike
4,256412
$endgroup$
add a comment |
$begingroup$
Yes. In fact we can establish something more general. Let $r$ be any positive integer and let $p_1,ldots, p_r$ be any $r$ primes. Next let $a$ an integer. Suppose $a^l equiv 1$ $mod p_1p_2ldots p_r$ (and note that $a$ does not have to be 2). Then $a^l = 1 + m(p_1 ldots p_r)$ $=1 +(mp_2p_3 ldots)p_1$ which implies that $a^l equiv 1$ mod $p_1$.
answered Jan 23 at 0:06
MikeMike
4,256412
$endgroup$
add a comment |
$begingroup$
Yes. In fact we can establish something more general. Let $r$ be any positive integer and let $p_1,ldots, p_r$ be any $r$ primes. Next let $a$ an integer. Suppose $a^l equiv 1$ $mod p_1p_2ldots p_r$ (and note that $a$ does not have to be 2). Then $a^l = 1 + m(p_1 ldots p_r)$ $=1 +(mp_2p_3 ldots)p_1$ which implies that $a^l equiv 1$ mod $p_1$.
answered Jan 23 at 0:06
MikeMike
4,256412
$endgroup$
Yes. In fact we can establish something more general. Let $r$ be any positive integer and let $p_1,ldots, p_r$ be any $r$ primes. Next let $a$ an integer. Suppose $a^l equiv 1$ $mod p_1p_2ldots p_r$ (and note that $a$ does not have to be 2). Then $a^l = 1 + m(p_1 ldots p_r)$ $=1 +(mp_2p_3 ldots)p_1$ which implies that $a^l equiv 1$ mod $p_1$.
answered Jan 23 at 0:06
MikeMike
4,256412
answered Jan 23 at 0:06
MikeMike
4,256412
answered Jan 23 at 0:06
MikeMike
4,256412
answered Jan 23 at 0:06
MikeMike
4,256412
4,256412
add a comment |
add a comment |
$begingroup$
Yes. More generally:
If $phi: G to G'$ is a group homomorphism and $g in G$ has finite order, then $o(phi(g))$ divides $o(g)$.
See a proof here.
This general fact applies to your case because $x bmod n mapsto x bmod d$ defines a group homomorphism $mathbb Z_n^times to mathbb Z_d^times$ if $d$ divides $n$.
answered Jan 23 at 0:17
lhflhf
166k10171396
$endgroup$
add a comment |
$begingroup$
Yes. More generally:
If $phi: G to G'$ is a group homomorphism and $g in G$ has finite order, then $o(phi(g))$ divides $o(g)$.
See a proof here.
This general fact applies to your case because $x bmod n mapsto x bmod d$ defines a group homomorphism $mathbb Z_n^times to mathbb Z_d^times$ if $d$ divides $n$.
answered Jan 23 at 0:17
lhflhf
166k10171396
$endgroup$
add a comment |
$begingroup$
Yes. More generally:
If $phi: G to G'$ is a group homomorphism and $g in G$ has finite order, then $o(phi(g))$ divides $o(g)$.
See a proof here.
This general fact applies to your case because $x bmod n mapsto x bmod d$ defines a group homomorphism $mathbb Z_n^times to mathbb Z_d^times$ if $d$ divides $n$.
answered Jan 23 at 0:17
lhflhf
166k10171396
$endgroup$
Yes. More generally:
If $phi: G to G'$ is a group homomorphism and $g in G$ has finite order, then $o(phi(g))$ divides $o(g)$.
See a proof here.
This general fact applies to your case because $x bmod n mapsto x bmod d$ defines a group homomorphism $mathbb Z_n^times to mathbb Z_d^times$ if $d$ divides $n$.
answered Jan 23 at 0:17
lhflhf
166k10171396
answered Jan 23 at 0:17
lhflhf
166k10171396
answered Jan 23 at 0:17
lhflhf
166k10171396
answered Jan 23 at 0:17
lhflhf
166k10171396
166k10171396
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%2f3083843%2fdoes-the-order-of-2-in-z-p-divide-the-order-of-2-in-z-n%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
