For what $n$ is $U_n$ cyclic?
$begingroup$
When can we say a multiplicative group of integers modulo $n$, i.e., $U_n$ is cyclic?
$$U_n={a inmathbb Z_n mid gcd(a,n)=1 }$$
I searched the internet but did not get a clear idea.
abstract-algebra group-theory cyclic-groups
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
asked Feb 26 '13 at 12:58
SankhaSankha
595722
$endgroup$
add a comment |
$begingroup$
When can we say a multiplicative group of integers modulo $n$, i.e., $U_n$ is cyclic?
$$U_n={a inmathbb Z_n mid gcd(a,n)=1 }$$
I searched the internet but did not get a clear idea.
abstract-algebra group-theory cyclic-groups
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
asked Feb 26 '13 at 12:58
SankhaSankha
595722
$endgroup$
add a comment |
$begingroup$
When can we say a multiplicative group of integers modulo $n$, i.e., $U_n$ is cyclic?
$$U_n={a inmathbb Z_n mid gcd(a,n)=1 }$$
I searched the internet but did not get a clear idea.
abstract-algebra group-theory cyclic-groups
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
asked Feb 26 '13 at 12:58
SankhaSankha
595722
$endgroup$
When can we say a multiplicative group of integers modulo $n$, i.e., $U_n$ is cyclic?
$$U_n={a inmathbb Z_n mid gcd(a,n)=1 }$$
I searched the internet but did not get a clear idea.
abstract-algebra group-theory cyclic-groups
abstract-algebra group-theory cyclic-groups
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
asked Feb 26 '13 at 12:58
SankhaSankha
595722
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
asked Feb 26 '13 at 12:58
SankhaSankha
595722
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
edited Feb 7 '16 at 11:17
Rudy the Reindeer
26.8k1796245
26.8k1796245
asked Feb 26 '13 at 12:58
SankhaSankha
595722
asked Feb 26 '13 at 12:58
SankhaSankha
595722
asked Feb 26 '13 at 12:58
SankhaSankha
595722
595722
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
So $U_n$ is the group of units in $mathbb{Z}/nmathbb{Z}$.
Write the prime decomposition
$$
n=p_1^{alpha_1}cdots p_r^{alpha_r}.
$$
By the Chinese remainder theorem
$$
mathbb{Z}/nmathbb{Z}=mathbb{Z}/p_1^{alpha_1}mathbb{Z}timesldotstimesmathbb{Z}/p_r^{alpha_r}mathbb{Z}
$$
so
$$
U_n=U_{p_1^{alpha_1}}timesldotstimes U_{p_r^{alpha_r}}.
$$
For powers of $2$, we have
$$
U_2={0}
$$
and for $kgeq 2$
$$
U_{2^k}=mathbb{Z}/2mathbb{Z}times mathbb{Z}/2^{k-2}mathbb{Z}.
$$
For odd primes $p$,
$$
U_{p^alpha}=mathbb{Z}/phi(p^alpha)mathbb{Z}=mathbb{Z}/p^{alpha-1}(p-1)mathbb{Z}.
$$
So you see now that $U_n$ is cyclic if and only if
$$
n=2,4,p^alpha,2p^{alpha}
$$
where $p$ is an odd prime.
Here is a reference.
edited Mar 18 '16 at 21:25
user26857
39.5k124284
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
$endgroup$
2
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
add a comment |
$begingroup$
$U_n$ is cyclic iff $n$ is $2$, $4$, $p^k$, or $2p^k$, where $p$ is an odd prime.
The proof follows from the Chinese Remainder Theorem for rings and the fact that $C_m times C_n$ is cyclic iff $(m,n)=1$ (here $C_n$ is the cyclic group of order $n$).
The hard part is proving that $U_p$ is cyclic and this follows from the fact that $mathbb Z/p$ is a field and that $n = sum_{dmid n} phi(d)$.
Any book on elementary number theory has a proof of this theorem. See for instance André Weil's Number theory for beginners, Leveque's Fundamentals of Number Theory, and Bolker's Elementary Number Theory.
edited Feb 26 '13 at 14:59
Michael Hardy
1
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
$endgroup$
add a comment |
$begingroup$
Here "cyclic if and only if $varphi(n)=lambda(n)$" but there's no proof - the proof is elementary but very tricky.
$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%2f314846%2ffor-what-n-is-u-n-cyclic%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$
So $U_n$ is the group of units in $mathbb{Z}/nmathbb{Z}$.
Write the prime decomposition
$$
n=p_1^{alpha_1}cdots p_r^{alpha_r}.
$$
By the Chinese remainder theorem
$$
mathbb{Z}/nmathbb{Z}=mathbb{Z}/p_1^{alpha_1}mathbb{Z}timesldotstimesmathbb{Z}/p_r^{alpha_r}mathbb{Z}
$$
so
$$
U_n=U_{p_1^{alpha_1}}timesldotstimes U_{p_r^{alpha_r}}.
$$
For powers of $2$, we have
$$
U_2={0}
$$
and for $kgeq 2$
$$
U_{2^k}=mathbb{Z}/2mathbb{Z}times mathbb{Z}/2^{k-2}mathbb{Z}.
$$
For odd primes $p$,
$$
U_{p^alpha}=mathbb{Z}/phi(p^alpha)mathbb{Z}=mathbb{Z}/p^{alpha-1}(p-1)mathbb{Z}.
$$
So you see now that $U_n$ is cyclic if and only if
$$
n=2,4,p^alpha,2p^{alpha}
$$
where $p$ is an odd prime.
Here is a reference.
edited Mar 18 '16 at 21:25
user26857
39.5k124284
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
$endgroup$
2
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
add a comment |
$begingroup$
So $U_n$ is the group of units in $mathbb{Z}/nmathbb{Z}$.
Write the prime decomposition
$$
n=p_1^{alpha_1}cdots p_r^{alpha_r}.
$$
By the Chinese remainder theorem
$$
mathbb{Z}/nmathbb{Z}=mathbb{Z}/p_1^{alpha_1}mathbb{Z}timesldotstimesmathbb{Z}/p_r^{alpha_r}mathbb{Z}
$$
so
$$
U_n=U_{p_1^{alpha_1}}timesldotstimes U_{p_r^{alpha_r}}.
$$
For powers of $2$, we have
$$
U_2={0}
$$
and for $kgeq 2$
$$
U_{2^k}=mathbb{Z}/2mathbb{Z}times mathbb{Z}/2^{k-2}mathbb{Z}.
$$
For odd primes $p$,
$$
U_{p^alpha}=mathbb{Z}/phi(p^alpha)mathbb{Z}=mathbb{Z}/p^{alpha-1}(p-1)mathbb{Z}.
$$
So you see now that $U_n$ is cyclic if and only if
$$
n=2,4,p^alpha,2p^{alpha}
$$
where $p$ is an odd prime.
Here is a reference.
edited Mar 18 '16 at 21:25
user26857
39.5k124284
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
$endgroup$
2
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
add a comment |
$begingroup$
So $U_n$ is the group of units in $mathbb{Z}/nmathbb{Z}$.
Write the prime decomposition
$$
n=p_1^{alpha_1}cdots p_r^{alpha_r}.
$$
By the Chinese remainder theorem
$$
mathbb{Z}/nmathbb{Z}=mathbb{Z}/p_1^{alpha_1}mathbb{Z}timesldotstimesmathbb{Z}/p_r^{alpha_r}mathbb{Z}
$$
so
$$
U_n=U_{p_1^{alpha_1}}timesldotstimes U_{p_r^{alpha_r}}.
$$
For powers of $2$, we have
$$
U_2={0}
$$
and for $kgeq 2$
$$
U_{2^k}=mathbb{Z}/2mathbb{Z}times mathbb{Z}/2^{k-2}mathbb{Z}.
$$
For odd primes $p$,
$$
U_{p^alpha}=mathbb{Z}/phi(p^alpha)mathbb{Z}=mathbb{Z}/p^{alpha-1}(p-1)mathbb{Z}.
$$
So you see now that $U_n$ is cyclic if and only if
$$
n=2,4,p^alpha,2p^{alpha}
$$
where $p$ is an odd prime.
Here is a reference.
edited Mar 18 '16 at 21:25
user26857
39.5k124284
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
$endgroup$
So $U_n$ is the group of units in $mathbb{Z}/nmathbb{Z}$.
Write the prime decomposition
$$
n=p_1^{alpha_1}cdots p_r^{alpha_r}.
$$
By the Chinese remainder theorem
$$
mathbb{Z}/nmathbb{Z}=mathbb{Z}/p_1^{alpha_1}mathbb{Z}timesldotstimesmathbb{Z}/p_r^{alpha_r}mathbb{Z}
$$
so
$$
U_n=U_{p_1^{alpha_1}}timesldotstimes U_{p_r^{alpha_r}}.
$$
For powers of $2$, we have
$$
U_2={0}
$$
and for $kgeq 2$
$$
U_{2^k}=mathbb{Z}/2mathbb{Z}times mathbb{Z}/2^{k-2}mathbb{Z}.
$$
For odd primes $p$,
$$
U_{p^alpha}=mathbb{Z}/phi(p^alpha)mathbb{Z}=mathbb{Z}/p^{alpha-1}(p-1)mathbb{Z}.
$$
So you see now that $U_n$ is cyclic if and only if
$$
n=2,4,p^alpha,2p^{alpha}
$$
where $p$ is an odd prime.
Here is a reference.
edited Mar 18 '16 at 21:25
user26857
39.5k124284
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
edited Mar 18 '16 at 21:25
user26857
39.5k124284
edited Mar 18 '16 at 21:25
user26857
39.5k124284
edited Mar 18 '16 at 21:25
user26857
39.5k124284
39.5k124284
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
answered Feb 26 '13 at 13:24
JulienJulien
38.8k358131
38.8k358131
2
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
add a comment |
2
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
2
2
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Why is it true that $U_{p^k}=mathbb{Z}/2mathbb{Z}timesmathbb{Z}/2^{k-2}mathbb{Z}$?
$endgroup$
– Rasputin
Jan 20 '17 at 20:03
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
$begingroup$
Julien, why doesn't the even prime work please?
$endgroup$
– BCLC
Oct 17 '18 at 11:48
add a comment |
$begingroup$
$U_n$ is cyclic iff $n$ is $2$, $4$, $p^k$, or $2p^k$, where $p$ is an odd prime.
The proof follows from the Chinese Remainder Theorem for rings and the fact that $C_m times C_n$ is cyclic iff $(m,n)=1$ (here $C_n$ is the cyclic group of order $n$).
The hard part is proving that $U_p$ is cyclic and this follows from the fact that $mathbb Z/p$ is a field and that $n = sum_{dmid n} phi(d)$.
Any book on elementary number theory has a proof of this theorem. See for instance André Weil's Number theory for beginners, Leveque's Fundamentals of Number Theory, and Bolker's Elementary Number Theory.
edited Feb 26 '13 at 14:59
Michael Hardy
1
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
$endgroup$
add a comment |
$begingroup$
$U_n$ is cyclic iff $n$ is $2$, $4$, $p^k$, or $2p^k$, where $p$ is an odd prime.
The proof follows from the Chinese Remainder Theorem for rings and the fact that $C_m times C_n$ is cyclic iff $(m,n)=1$ (here $C_n$ is the cyclic group of order $n$).
The hard part is proving that $U_p$ is cyclic and this follows from the fact that $mathbb Z/p$ is a field and that $n = sum_{dmid n} phi(d)$.
Any book on elementary number theory has a proof of this theorem. See for instance André Weil's Number theory for beginners, Leveque's Fundamentals of Number Theory, and Bolker's Elementary Number Theory.
edited Feb 26 '13 at 14:59
Michael Hardy
1
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
$endgroup$
add a comment |
$begingroup$
$U_n$ is cyclic iff $n$ is $2$, $4$, $p^k$, or $2p^k$, where $p$ is an odd prime.
The proof follows from the Chinese Remainder Theorem for rings and the fact that $C_m times C_n$ is cyclic iff $(m,n)=1$ (here $C_n$ is the cyclic group of order $n$).
The hard part is proving that $U_p$ is cyclic and this follows from the fact that $mathbb Z/p$ is a field and that $n = sum_{dmid n} phi(d)$.
Any book on elementary number theory has a proof of this theorem. See for instance André Weil's Number theory for beginners, Leveque's Fundamentals of Number Theory, and Bolker's Elementary Number Theory.
edited Feb 26 '13 at 14:59
Michael Hardy
1
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
$endgroup$
$U_n$ is cyclic iff $n$ is $2$, $4$, $p^k$, or $2p^k$, where $p$ is an odd prime.
The proof follows from the Chinese Remainder Theorem for rings and the fact that $C_m times C_n$ is cyclic iff $(m,n)=1$ (here $C_n$ is the cyclic group of order $n$).
The hard part is proving that $U_p$ is cyclic and this follows from the fact that $mathbb Z/p$ is a field and that $n = sum_{dmid n} phi(d)$.
Any book on elementary number theory has a proof of this theorem. See for instance André Weil's Number theory for beginners, Leveque's Fundamentals of Number Theory, and Bolker's Elementary Number Theory.
edited Feb 26 '13 at 14:59
Michael Hardy
1
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
edited Feb 26 '13 at 14:59
Michael Hardy
1
edited Feb 26 '13 at 14:59
Michael Hardy
1
edited Feb 26 '13 at 14:59
Michael Hardy
1
1
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
answered Feb 26 '13 at 13:11
lhflhf
167k11172404
167k11172404
add a comment |
add a comment |
$begingroup$
Here "cyclic if and only if $varphi(n)=lambda(n)$" but there's no proof - the proof is elementary but very tricky.
$endgroup$
add a comment |
$begingroup$
Here "cyclic if and only if $varphi(n)=lambda(n)$" but there's no proof - the proof is elementary but very tricky.
$endgroup$
add a comment |
$begingroup$
Here "cyclic if and only if $varphi(n)=lambda(n)$" but there's no proof - the proof is elementary but very tricky.
$endgroup$
Here "cyclic if and only if $varphi(n)=lambda(n)$" but there's no proof - the proof is elementary but very tricky.
edited Dec 16 '13 at 9:18
answered Feb 26 '13 at 13:07
user58512
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%2f314846%2ffor-what-n-is-u-n-cyclic%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
