Amount of generators for cyclic group and Euler's function
$begingroup$
I have this question, since I'm confused about this concept. Let's say I have a cyclic group, for example $mathbb{Z}_7^{times} = left{1, 2, 3, 4, 5, 6right}$. What is the relationship between the amount of generators for this group and $phi(7)$, with $phi$ Euler's function?
I found the generators as $left{3, 4, 5, 6 right}$. I know that if $G$ is a cyclic group of order $n$, and $g$ is a generator, then $g^s$ will also be a generator if and only if $gcd(s,n) = 1$. But then I read somewhere that if $n$ is prime (which in our case it is), then $phi(7) = 6$ and the amount of generators should be $6$? This cannot be true for the group $mathbb{Z}_7^{times}$, since $1$ cannot possibly be a generator for multiplication.
For example, if I have the cyclic group $mathbb{Z}_{13}^{times}$, what is the best method to find a generator, and to find how many there are?
abstract-algebra elementary-number-theory
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
$endgroup$
add a comment |
$begingroup$
I have this question, since I'm confused about this concept. Let's say I have a cyclic group, for example $mathbb{Z}_7^{times} = left{1, 2, 3, 4, 5, 6right}$. What is the relationship between the amount of generators for this group and $phi(7)$, with $phi$ Euler's function?
I found the generators as $left{3, 4, 5, 6 right}$. I know that if $G$ is a cyclic group of order $n$, and $g$ is a generator, then $g^s$ will also be a generator if and only if $gcd(s,n) = 1$. But then I read somewhere that if $n$ is prime (which in our case it is), then $phi(7) = 6$ and the amount of generators should be $6$? This cannot be true for the group $mathbb{Z}_7^{times}$, since $1$ cannot possibly be a generator for multiplication.
For example, if I have the cyclic group $mathbb{Z}_{13}^{times}$, what is the best method to find a generator, and to find how many there are?
abstract-algebra elementary-number-theory
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
$endgroup$
add a comment |
$begingroup$
I have this question, since I'm confused about this concept. Let's say I have a cyclic group, for example $mathbb{Z}_7^{times} = left{1, 2, 3, 4, 5, 6right}$. What is the relationship between the amount of generators for this group and $phi(7)$, with $phi$ Euler's function?
I found the generators as $left{3, 4, 5, 6 right}$. I know that if $G$ is a cyclic group of order $n$, and $g$ is a generator, then $g^s$ will also be a generator if and only if $gcd(s,n) = 1$. But then I read somewhere that if $n$ is prime (which in our case it is), then $phi(7) = 6$ and the amount of generators should be $6$? This cannot be true for the group $mathbb{Z}_7^{times}$, since $1$ cannot possibly be a generator for multiplication.
For example, if I have the cyclic group $mathbb{Z}_{13}^{times}$, what is the best method to find a generator, and to find how many there are?
abstract-algebra elementary-number-theory
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
$endgroup$
I have this question, since I'm confused about this concept. Let's say I have a cyclic group, for example $mathbb{Z}_7^{times} = left{1, 2, 3, 4, 5, 6right}$. What is the relationship between the amount of generators for this group and $phi(7)$, with $phi$ Euler's function?
I found the generators as $left{3, 4, 5, 6 right}$. I know that if $G$ is a cyclic group of order $n$, and $g$ is a generator, then $g^s$ will also be a generator if and only if $gcd(s,n) = 1$. But then I read somewhere that if $n$ is prime (which in our case it is), then $phi(7) = 6$ and the amount of generators should be $6$? This cannot be true for the group $mathbb{Z}_7^{times}$, since $1$ cannot possibly be a generator for multiplication.
For example, if I have the cyclic group $mathbb{Z}_{13}^{times}$, what is the best method to find a generator, and to find how many there are?
abstract-algebra elementary-number-theory
abstract-algebra elementary-number-theory
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
asked Aug 10 '16 at 14:53
KamilKamil
2,00221545
2,00221545
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A cyclic group with $n$ elements has $varphi(n)$ generators.
It seems like what you're getting confused by is that:
The group $mathbb{Z}_7^times={1,2,3,4,5,6}$ is a cyclic group with 6 elements, and therefore it should considered equivalent to (more precisely, it is isomorphic to) the cyclic group $mathbb{Z}_6$, and you should expect $varphi(6)=2$ generators, not $varphi(7)=6$ generators
The elements $4$ and $6$ in $mathbb{Z}_7^times$ are not generators: the powers of $4$ in $mathbb{Z}_7^times$ are ${1,4,2}$, and the powers of $6$ in $mathbb{Z}_7^times$ are ${1,6}$. (The only generators of $mathbb{Z}_7^times$ are $3$ and $5$, and there are exactly $2=varphi(6)$ of them.)
More generally, if $p$ is a prime number, then $mathbb{Z}_p$ is a cyclic group with $p$ elements, while $mathbb{Z}_p^times$ is a cyclic group with $p-1$ elements, so $mathbb{Z}_p^times$ has $varphi(p-1)$ generators.
As for the best method to find a generator, that is a far more advanced problem.
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
$endgroup$
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
add a comment |
$begingroup$
As for
best method to find a generator, that is a far more advanced problem
There is fine way to find generators:
For example lets take Z×22.
1. Z×22 = {1,3,5,7,9,13,15,17,19,21}
2. φ(22) = 10 = 5*2
3. Find the first generator(7) and remember the order it generates the group in:
{1:7, 2:5, 3:13, 5:13, 5:21, 6:15, 7:17, 8:19, 9:19, 10:1}
4. Take all elements which indexes have gcd(5, index) = gcd(2, index) = 1.
5. They are: {7,13,17,19} - that will be your generators.
answered Jan 14 at 20:01
AseNAseN
1036
$endgroup$
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
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%2f1888229%2famount-of-generators-for-cyclic-group-and-eulers-function%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$
A cyclic group with $n$ elements has $varphi(n)$ generators.
It seems like what you're getting confused by is that:
The group $mathbb{Z}_7^times={1,2,3,4,5,6}$ is a cyclic group with 6 elements, and therefore it should considered equivalent to (more precisely, it is isomorphic to) the cyclic group $mathbb{Z}_6$, and you should expect $varphi(6)=2$ generators, not $varphi(7)=6$ generators
The elements $4$ and $6$ in $mathbb{Z}_7^times$ are not generators: the powers of $4$ in $mathbb{Z}_7^times$ are ${1,4,2}$, and the powers of $6$ in $mathbb{Z}_7^times$ are ${1,6}$. (The only generators of $mathbb{Z}_7^times$ are $3$ and $5$, and there are exactly $2=varphi(6)$ of them.)
More generally, if $p$ is a prime number, then $mathbb{Z}_p$ is a cyclic group with $p$ elements, while $mathbb{Z}_p^times$ is a cyclic group with $p-1$ elements, so $mathbb{Z}_p^times$ has $varphi(p-1)$ generators.
As for the best method to find a generator, that is a far more advanced problem.
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
$endgroup$
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
add a comment |
$begingroup$
A cyclic group with $n$ elements has $varphi(n)$ generators.
It seems like what you're getting confused by is that:
The group $mathbb{Z}_7^times={1,2,3,4,5,6}$ is a cyclic group with 6 elements, and therefore it should considered equivalent to (more precisely, it is isomorphic to) the cyclic group $mathbb{Z}_6$, and you should expect $varphi(6)=2$ generators, not $varphi(7)=6$ generators
The elements $4$ and $6$ in $mathbb{Z}_7^times$ are not generators: the powers of $4$ in $mathbb{Z}_7^times$ are ${1,4,2}$, and the powers of $6$ in $mathbb{Z}_7^times$ are ${1,6}$. (The only generators of $mathbb{Z}_7^times$ are $3$ and $5$, and there are exactly $2=varphi(6)$ of them.)
More generally, if $p$ is a prime number, then $mathbb{Z}_p$ is a cyclic group with $p$ elements, while $mathbb{Z}_p^times$ is a cyclic group with $p-1$ elements, so $mathbb{Z}_p^times$ has $varphi(p-1)$ generators.
As for the best method to find a generator, that is a far more advanced problem.
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
$endgroup$
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
add a comment |
$begingroup$
A cyclic group with $n$ elements has $varphi(n)$ generators.
It seems like what you're getting confused by is that:
The group $mathbb{Z}_7^times={1,2,3,4,5,6}$ is a cyclic group with 6 elements, and therefore it should considered equivalent to (more precisely, it is isomorphic to) the cyclic group $mathbb{Z}_6$, and you should expect $varphi(6)=2$ generators, not $varphi(7)=6$ generators
The elements $4$ and $6$ in $mathbb{Z}_7^times$ are not generators: the powers of $4$ in $mathbb{Z}_7^times$ are ${1,4,2}$, and the powers of $6$ in $mathbb{Z}_7^times$ are ${1,6}$. (The only generators of $mathbb{Z}_7^times$ are $3$ and $5$, and there are exactly $2=varphi(6)$ of them.)
More generally, if $p$ is a prime number, then $mathbb{Z}_p$ is a cyclic group with $p$ elements, while $mathbb{Z}_p^times$ is a cyclic group with $p-1$ elements, so $mathbb{Z}_p^times$ has $varphi(p-1)$ generators.
As for the best method to find a generator, that is a far more advanced problem.
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
$endgroup$
A cyclic group with $n$ elements has $varphi(n)$ generators.
It seems like what you're getting confused by is that:
The group $mathbb{Z}_7^times={1,2,3,4,5,6}$ is a cyclic group with 6 elements, and therefore it should considered equivalent to (more precisely, it is isomorphic to) the cyclic group $mathbb{Z}_6$, and you should expect $varphi(6)=2$ generators, not $varphi(7)=6$ generators
The elements $4$ and $6$ in $mathbb{Z}_7^times$ are not generators: the powers of $4$ in $mathbb{Z}_7^times$ are ${1,4,2}$, and the powers of $6$ in $mathbb{Z}_7^times$ are ${1,6}$. (The only generators of $mathbb{Z}_7^times$ are $3$ and $5$, and there are exactly $2=varphi(6)$ of them.)
More generally, if $p$ is a prime number, then $mathbb{Z}_p$ is a cyclic group with $p$ elements, while $mathbb{Z}_p^times$ is a cyclic group with $p-1$ elements, so $mathbb{Z}_p^times$ has $varphi(p-1)$ generators.
As for the best method to find a generator, that is a far more advanced problem.
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
edited Aug 10 '16 at 15:08
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
answered Aug 10 '16 at 15:01
Zev ChonolesZev Chonoles
110k16228426
110k16228426
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
add a comment |
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
$begingroup$
Ah yes, now I understand! That was exactly my confusion. Thanks for pointing out this important piece of information!
$endgroup$
– Kamil
Aug 10 '16 at 15:07
add a comment |
$begingroup$
As for
best method to find a generator, that is a far more advanced problem
There is fine way to find generators:
For example lets take Z×22.
1. Z×22 = {1,3,5,7,9,13,15,17,19,21}
2. φ(22) = 10 = 5*2
3. Find the first generator(7) and remember the order it generates the group in:
{1:7, 2:5, 3:13, 5:13, 5:21, 6:15, 7:17, 8:19, 9:19, 10:1}
4. Take all elements which indexes have gcd(5, index) = gcd(2, index) = 1.
5. They are: {7,13,17,19} - that will be your generators.
answered Jan 14 at 20:01
AseNAseN
1036
$endgroup$
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
add a comment |
$begingroup$
As for
best method to find a generator, that is a far more advanced problem
There is fine way to find generators:
For example lets take Z×22.
1. Z×22 = {1,3,5,7,9,13,15,17,19,21}
2. φ(22) = 10 = 5*2
3. Find the first generator(7) and remember the order it generates the group in:
{1:7, 2:5, 3:13, 5:13, 5:21, 6:15, 7:17, 8:19, 9:19, 10:1}
4. Take all elements which indexes have gcd(5, index) = gcd(2, index) = 1.
5. They are: {7,13,17,19} - that will be your generators.
answered Jan 14 at 20:01
AseNAseN
1036
$endgroup$
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
add a comment |
$begingroup$
As for
best method to find a generator, that is a far more advanced problem
There is fine way to find generators:
For example lets take Z×22.
1. Z×22 = {1,3,5,7,9,13,15,17,19,21}
2. φ(22) = 10 = 5*2
3. Find the first generator(7) and remember the order it generates the group in:
{1:7, 2:5, 3:13, 5:13, 5:21, 6:15, 7:17, 8:19, 9:19, 10:1}
4. Take all elements which indexes have gcd(5, index) = gcd(2, index) = 1.
5. They are: {7,13,17,19} - that will be your generators.
answered Jan 14 at 20:01
AseNAseN
1036
$endgroup$
As for
best method to find a generator, that is a far more advanced problem
There is fine way to find generators:
For example lets take Z×22.
1. Z×22 = {1,3,5,7,9,13,15,17,19,21}
2. φ(22) = 10 = 5*2
3. Find the first generator(7) and remember the order it generates the group in:
{1:7, 2:5, 3:13, 5:13, 5:21, 6:15, 7:17, 8:19, 9:19, 10:1}
4. Take all elements which indexes have gcd(5, index) = gcd(2, index) = 1.
5. They are: {7,13,17,19} - that will be your generators.
answered Jan 14 at 20:01
AseNAseN
1036
edited Jan 14 at 20:07
answered Jan 14 at 20:01
AseNAseN
1036
answered Jan 14 at 20:01
AseNAseN
1036
answered Jan 14 at 20:01
AseNAseN
1036
1036
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
add a comment |
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
But "find the first generator" is the whole problem.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:08
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
Yes, noticed that during applying this method. But it can definitly reduce the total time of searching each generator.
$endgroup$
– AseN
Jan 14 at 20:13
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
$begingroup$
What can? You mean this method of finding all generators? Because that seems like it is precisely the standard way where you take all powers of a fixed generator which are coprime to the order.
$endgroup$
– Tobias Kildetoft
Jan 14 at 20:16
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%2f1888229%2famount-of-generators-for-cyclic-group-and-eulers-function%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
