Cyclic Group Generators of Order $n$












2














How many generators does a cyclic group of order $n$ have? I know that a cyclic group can be generated by just one element while using the operation of the group. I am having trouble coming up with the generators of a group of order $n$.



Any help would be great! Thanks!










share|cite|improve this question
























  • Why would $n$ not be finite?
    – Tobias Kildetoft
    Feb 21 '17 at 19:45
















2














How many generators does a cyclic group of order $n$ have? I know that a cyclic group can be generated by just one element while using the operation of the group. I am having trouble coming up with the generators of a group of order $n$.



Any help would be great! Thanks!










share|cite|improve this question
























  • Why would $n$ not be finite?
    – Tobias Kildetoft
    Feb 21 '17 at 19:45














2












2








2


0





How many generators does a cyclic group of order $n$ have? I know that a cyclic group can be generated by just one element while using the operation of the group. I am having trouble coming up with the generators of a group of order $n$.



Any help would be great! Thanks!










share|cite|improve this question















How many generators does a cyclic group of order $n$ have? I know that a cyclic group can be generated by just one element while using the operation of the group. I am having trouble coming up with the generators of a group of order $n$.



Any help would be great! Thanks!







abstract-algebra group-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 21 '17 at 20:00







wolf

















asked Feb 21 '17 at 19:44









wolfwolf

413




413












  • Why would $n$ not be finite?
    – Tobias Kildetoft
    Feb 21 '17 at 19:45


















  • Why would $n$ not be finite?
    – Tobias Kildetoft
    Feb 21 '17 at 19:45
















Why would $n$ not be finite?
– Tobias Kildetoft
Feb 21 '17 at 19:45




Why would $n$ not be finite?
– Tobias Kildetoft
Feb 21 '17 at 19:45










4 Answers
4






active

oldest

votes


















5














Suppose $G$ is a cylcic group of order $n$, then there is at least one $g in G$ such that the order of $g$ equals $n$, that is: $g^n = e$ and $g^k neq e$ for $0 leq k < n$. Let us prove that the elements of the following set
$${g^s : : vert : : 0 leq s < n, text{gcd}(s,n) = 1}$$
are all generators of $G$.



In order to prove this claim, we need to show that the order of $g^s$ is exactly $n$. Suppose that it is $k$, where $0 < k leq n$. We have that
begin{equation}
(g^s)^n = (g^n)^s = e
end{equation}
and therefore we must have that $k$ divides $n$. Let us now prove that $n$ divides $k$. Because of Euclids lemma, there are $q, r in mathbb{N}$ such that $k = qn + r$, where $0 leq r < n$. We have that
begin{equation}
e = (g^s)^k = (g^s)^{qn} cdot (g^s)^r = (g^s)^r = g^{sr}.
end{equation}
Since the order of $g$ is $n$, we must have that $n$ divides $sr$. However, because $text{gcd}(s,n) = 1$, we must have that $n$ divides $r$, but this would mean that either $n leq r$ (impossible because of $0 leq r < n$) or $r = 0$. Since $r = 0$ is the only possibility, we have that $k = qn$, so $n$ divides $k$ and therefore we must have that $k = n$. So $g^s$ is a generator of $G$ in the case that $text{gcd}(s,n) = 1$.



This proves the claim made in the answer of E.Joseph, that there are exactly $varphi(n)$ generators (since $varphi(n)$ is exactly the number of elements which are coprime to $n$). It also gives you an idea on how to find all generators, given that you know one generator.






share|cite|improve this answer





















  • I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
    – Alex M.
    Feb 21 '17 at 20:44










  • No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
    – Student
    Feb 21 '17 at 20:52












  • Student, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03










  • I didn't understand why is it must that $n$ divides $r$? @Student
    – J. Doe
    Oct 30 '18 at 16:09










  • @J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
    – Student
    Oct 30 '18 at 17:34



















4














Let $g$ be a generator of $G$. Let $g^m$ be another generator, with $2 le m le n-1$. This means that $(g^m)^k ne e$ for all $1 le k le n-1$, i.e. $n nmid mk$ for all $1 le k le n-1$.



If $gcd(n,m) = d > 1$ then, letting $m = da$ and $n = db$, the above condition becomes $b nmid ak$ for all $1 le k le n-1$. Since $d>1$, it follows that $b<n$, so if you choose $k=b$ you get $b mid ab$, which is contradicts the assumption that $n nmid mk$ for all $1 le k le n-1$. It follows that, necessarily, $gcd(n,m) = 1$.



Let us show that the condition $gcd(m,n) = 1$ is also sufficient for $g^m$ to be a generator. Assume there exist $2 le k le n-1$ with $(g^m)^k = e$. Since $gcd(m,n) = 1$, by Bézout's theorem there exist $s,t in Bbb Z$ such that $sm + tn = 1$, which implies $smk + tnk = k$, whence it follows that



$$e = e^s = (g^{mk})^s = g^{mks} = g^{k - tnk} = g^k (g^n)^{-tk} = g^k ,$$



so $g^k = e$, which contradicts the fact that $g$ is a generator.



We have discovered that in order for $g^m$ to be a generator, it is necessary and sufficient that $gcd(m,n)=1$, for $2 le m le n-1$. How many numbers coprime with $n$ do we have in ${2, 3, dots, n-1}$? By definition, $varphi(n)-1$, where $varphi$ is Euler's totient function. We have a "$-1$" because we start counting from $m=2$; taking into consideration that $g$ is a generator, too, and it corresponds to $m=1$, we get a total of $varphi(n)$ generators.






share|cite|improve this answer





















  • Alex M., what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03



















3














A cyclic group of order $n$ has exactly $varphi(n)$ generators where $varphi$ is Euler's totient function.



This is the number of $kin{0,ldots,n-1}$ such that:



$$gcd(k,n)=1.$$



You can find an explicit expression:



$$varphi(n)=nprod_{pmid n}left(1-frac 1pright).$$






share|cite|improve this answer





















  • E. Joseph, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03



















2














Suppose $g$ is a generator of $G$, then any element in $G$ may be written $g^b$. Now we only have to figure out which $b$'s make $g^b$ a generator.



If $g^b$ is a generator, then $(g^b)^n=g^{bn}=e$, and $$(g^b)^1neq e\(g^b)^2neq e\(g^b)^3neq e\dots\(g^b)^{n-1}neq e$$ This means that $b,n$ have no common factor, that is $gcd(b,n)=1$. So every $b$, for which $gcd(b,n)=1$, makes $g^b$ a generator of $G$. The number of generators is therefore $$phi(n)=|{kmid 1leq k< n,gcd(k,n)=1}|$$






share|cite|improve this answer





















  • 1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
    – ikoikoia
    Oct 30 '18 at 10:15












  • @ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
    – cansomeonehelpmeout
    Oct 30 '18 at 11:20













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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2155137%2fcyclic-group-generators-of-order-n%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























4 Answers
4






active

oldest

votes








4 Answers
4






active

oldest

votes









active

oldest

votes






active

oldest

votes









5














Suppose $G$ is a cylcic group of order $n$, then there is at least one $g in G$ such that the order of $g$ equals $n$, that is: $g^n = e$ and $g^k neq e$ for $0 leq k < n$. Let us prove that the elements of the following set
$${g^s : : vert : : 0 leq s < n, text{gcd}(s,n) = 1}$$
are all generators of $G$.



In order to prove this claim, we need to show that the order of $g^s$ is exactly $n$. Suppose that it is $k$, where $0 < k leq n$. We have that
begin{equation}
(g^s)^n = (g^n)^s = e
end{equation}
and therefore we must have that $k$ divides $n$. Let us now prove that $n$ divides $k$. Because of Euclids lemma, there are $q, r in mathbb{N}$ such that $k = qn + r$, where $0 leq r < n$. We have that
begin{equation}
e = (g^s)^k = (g^s)^{qn} cdot (g^s)^r = (g^s)^r = g^{sr}.
end{equation}
Since the order of $g$ is $n$, we must have that $n$ divides $sr$. However, because $text{gcd}(s,n) = 1$, we must have that $n$ divides $r$, but this would mean that either $n leq r$ (impossible because of $0 leq r < n$) or $r = 0$. Since $r = 0$ is the only possibility, we have that $k = qn$, so $n$ divides $k$ and therefore we must have that $k = n$. So $g^s$ is a generator of $G$ in the case that $text{gcd}(s,n) = 1$.



This proves the claim made in the answer of E.Joseph, that there are exactly $varphi(n)$ generators (since $varphi(n)$ is exactly the number of elements which are coprime to $n$). It also gives you an idea on how to find all generators, given that you know one generator.






share|cite|improve this answer





















  • I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
    – Alex M.
    Feb 21 '17 at 20:44










  • No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
    – Student
    Feb 21 '17 at 20:52












  • Student, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03










  • I didn't understand why is it must that $n$ divides $r$? @Student
    – J. Doe
    Oct 30 '18 at 16:09










  • @J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
    – Student
    Oct 30 '18 at 17:34
















5














Suppose $G$ is a cylcic group of order $n$, then there is at least one $g in G$ such that the order of $g$ equals $n$, that is: $g^n = e$ and $g^k neq e$ for $0 leq k < n$. Let us prove that the elements of the following set
$${g^s : : vert : : 0 leq s < n, text{gcd}(s,n) = 1}$$
are all generators of $G$.



In order to prove this claim, we need to show that the order of $g^s$ is exactly $n$. Suppose that it is $k$, where $0 < k leq n$. We have that
begin{equation}
(g^s)^n = (g^n)^s = e
end{equation}
and therefore we must have that $k$ divides $n$. Let us now prove that $n$ divides $k$. Because of Euclids lemma, there are $q, r in mathbb{N}$ such that $k = qn + r$, where $0 leq r < n$. We have that
begin{equation}
e = (g^s)^k = (g^s)^{qn} cdot (g^s)^r = (g^s)^r = g^{sr}.
end{equation}
Since the order of $g$ is $n$, we must have that $n$ divides $sr$. However, because $text{gcd}(s,n) = 1$, we must have that $n$ divides $r$, but this would mean that either $n leq r$ (impossible because of $0 leq r < n$) or $r = 0$. Since $r = 0$ is the only possibility, we have that $k = qn$, so $n$ divides $k$ and therefore we must have that $k = n$. So $g^s$ is a generator of $G$ in the case that $text{gcd}(s,n) = 1$.



This proves the claim made in the answer of E.Joseph, that there are exactly $varphi(n)$ generators (since $varphi(n)$ is exactly the number of elements which are coprime to $n$). It also gives you an idea on how to find all generators, given that you know one generator.






share|cite|improve this answer





















  • I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
    – Alex M.
    Feb 21 '17 at 20:44










  • No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
    – Student
    Feb 21 '17 at 20:52












  • Student, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03










  • I didn't understand why is it must that $n$ divides $r$? @Student
    – J. Doe
    Oct 30 '18 at 16:09










  • @J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
    – Student
    Oct 30 '18 at 17:34














5












5








5






Suppose $G$ is a cylcic group of order $n$, then there is at least one $g in G$ such that the order of $g$ equals $n$, that is: $g^n = e$ and $g^k neq e$ for $0 leq k < n$. Let us prove that the elements of the following set
$${g^s : : vert : : 0 leq s < n, text{gcd}(s,n) = 1}$$
are all generators of $G$.



In order to prove this claim, we need to show that the order of $g^s$ is exactly $n$. Suppose that it is $k$, where $0 < k leq n$. We have that
begin{equation}
(g^s)^n = (g^n)^s = e
end{equation}
and therefore we must have that $k$ divides $n$. Let us now prove that $n$ divides $k$. Because of Euclids lemma, there are $q, r in mathbb{N}$ such that $k = qn + r$, where $0 leq r < n$. We have that
begin{equation}
e = (g^s)^k = (g^s)^{qn} cdot (g^s)^r = (g^s)^r = g^{sr}.
end{equation}
Since the order of $g$ is $n$, we must have that $n$ divides $sr$. However, because $text{gcd}(s,n) = 1$, we must have that $n$ divides $r$, but this would mean that either $n leq r$ (impossible because of $0 leq r < n$) or $r = 0$. Since $r = 0$ is the only possibility, we have that $k = qn$, so $n$ divides $k$ and therefore we must have that $k = n$. So $g^s$ is a generator of $G$ in the case that $text{gcd}(s,n) = 1$.



This proves the claim made in the answer of E.Joseph, that there are exactly $varphi(n)$ generators (since $varphi(n)$ is exactly the number of elements which are coprime to $n$). It also gives you an idea on how to find all generators, given that you know one generator.






share|cite|improve this answer












Suppose $G$ is a cylcic group of order $n$, then there is at least one $g in G$ such that the order of $g$ equals $n$, that is: $g^n = e$ and $g^k neq e$ for $0 leq k < n$. Let us prove that the elements of the following set
$${g^s : : vert : : 0 leq s < n, text{gcd}(s,n) = 1}$$
are all generators of $G$.



In order to prove this claim, we need to show that the order of $g^s$ is exactly $n$. Suppose that it is $k$, where $0 < k leq n$. We have that
begin{equation}
(g^s)^n = (g^n)^s = e
end{equation}
and therefore we must have that $k$ divides $n$. Let us now prove that $n$ divides $k$. Because of Euclids lemma, there are $q, r in mathbb{N}$ such that $k = qn + r$, where $0 leq r < n$. We have that
begin{equation}
e = (g^s)^k = (g^s)^{qn} cdot (g^s)^r = (g^s)^r = g^{sr}.
end{equation}
Since the order of $g$ is $n$, we must have that $n$ divides $sr$. However, because $text{gcd}(s,n) = 1$, we must have that $n$ divides $r$, but this would mean that either $n leq r$ (impossible because of $0 leq r < n$) or $r = 0$. Since $r = 0$ is the only possibility, we have that $k = qn$, so $n$ divides $k$ and therefore we must have that $k = n$. So $g^s$ is a generator of $G$ in the case that $text{gcd}(s,n) = 1$.



This proves the claim made in the answer of E.Joseph, that there are exactly $varphi(n)$ generators (since $varphi(n)$ is exactly the number of elements which are coprime to $n$). It also gives you an idea on how to find all generators, given that you know one generator.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Feb 21 '17 at 20:30









StudentStudent

2,1121627




2,1121627












  • I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
    – Alex M.
    Feb 21 '17 at 20:44










  • No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
    – Student
    Feb 21 '17 at 20:52












  • Student, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03










  • I didn't understand why is it must that $n$ divides $r$? @Student
    – J. Doe
    Oct 30 '18 at 16:09










  • @J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
    – Student
    Oct 30 '18 at 17:34


















  • I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
    – Alex M.
    Feb 21 '17 at 20:44










  • No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
    – Student
    Feb 21 '17 at 20:52












  • Student, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03










  • I didn't understand why is it must that $n$ divides $r$? @Student
    – J. Doe
    Oct 30 '18 at 16:09










  • @J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
    – Student
    Oct 30 '18 at 17:34
















I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
– Alex M.
Feb 21 '17 at 20:44




I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work.
– Alex M.
Feb 21 '17 at 20:44












No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
– Student
Feb 21 '17 at 20:52






No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$).
– Student
Feb 21 '17 at 20:52














Student, what do you think of my proof please?
– BCLC
Aug 28 '18 at 6:03




Student, what do you think of my proof please?
– BCLC
Aug 28 '18 at 6:03












I didn't understand why is it must that $n$ divides $r$? @Student
– J. Doe
Oct 30 '18 at 16:09




I didn't understand why is it must that $n$ divides $r$? @Student
– J. Doe
Oct 30 '18 at 16:09












@J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
– Student
Oct 30 '18 at 17:34




@J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$.
– Student
Oct 30 '18 at 17:34











4














Let $g$ be a generator of $G$. Let $g^m$ be another generator, with $2 le m le n-1$. This means that $(g^m)^k ne e$ for all $1 le k le n-1$, i.e. $n nmid mk$ for all $1 le k le n-1$.



If $gcd(n,m) = d > 1$ then, letting $m = da$ and $n = db$, the above condition becomes $b nmid ak$ for all $1 le k le n-1$. Since $d>1$, it follows that $b<n$, so if you choose $k=b$ you get $b mid ab$, which is contradicts the assumption that $n nmid mk$ for all $1 le k le n-1$. It follows that, necessarily, $gcd(n,m) = 1$.



Let us show that the condition $gcd(m,n) = 1$ is also sufficient for $g^m$ to be a generator. Assume there exist $2 le k le n-1$ with $(g^m)^k = e$. Since $gcd(m,n) = 1$, by Bézout's theorem there exist $s,t in Bbb Z$ such that $sm + tn = 1$, which implies $smk + tnk = k$, whence it follows that



$$e = e^s = (g^{mk})^s = g^{mks} = g^{k - tnk} = g^k (g^n)^{-tk} = g^k ,$$



so $g^k = e$, which contradicts the fact that $g$ is a generator.



We have discovered that in order for $g^m$ to be a generator, it is necessary and sufficient that $gcd(m,n)=1$, for $2 le m le n-1$. How many numbers coprime with $n$ do we have in ${2, 3, dots, n-1}$? By definition, $varphi(n)-1$, where $varphi$ is Euler's totient function. We have a "$-1$" because we start counting from $m=2$; taking into consideration that $g$ is a generator, too, and it corresponds to $m=1$, we get a total of $varphi(n)$ generators.






share|cite|improve this answer





















  • Alex M., what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03
















4














Let $g$ be a generator of $G$. Let $g^m$ be another generator, with $2 le m le n-1$. This means that $(g^m)^k ne e$ for all $1 le k le n-1$, i.e. $n nmid mk$ for all $1 le k le n-1$.



If $gcd(n,m) = d > 1$ then, letting $m = da$ and $n = db$, the above condition becomes $b nmid ak$ for all $1 le k le n-1$. Since $d>1$, it follows that $b<n$, so if you choose $k=b$ you get $b mid ab$, which is contradicts the assumption that $n nmid mk$ for all $1 le k le n-1$. It follows that, necessarily, $gcd(n,m) = 1$.



Let us show that the condition $gcd(m,n) = 1$ is also sufficient for $g^m$ to be a generator. Assume there exist $2 le k le n-1$ with $(g^m)^k = e$. Since $gcd(m,n) = 1$, by Bézout's theorem there exist $s,t in Bbb Z$ such that $sm + tn = 1$, which implies $smk + tnk = k$, whence it follows that



$$e = e^s = (g^{mk})^s = g^{mks} = g^{k - tnk} = g^k (g^n)^{-tk} = g^k ,$$



so $g^k = e$, which contradicts the fact that $g$ is a generator.



We have discovered that in order for $g^m$ to be a generator, it is necessary and sufficient that $gcd(m,n)=1$, for $2 le m le n-1$. How many numbers coprime with $n$ do we have in ${2, 3, dots, n-1}$? By definition, $varphi(n)-1$, where $varphi$ is Euler's totient function. We have a "$-1$" because we start counting from $m=2$; taking into consideration that $g$ is a generator, too, and it corresponds to $m=1$, we get a total of $varphi(n)$ generators.






share|cite|improve this answer





















  • Alex M., what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03














4












4








4






Let $g$ be a generator of $G$. Let $g^m$ be another generator, with $2 le m le n-1$. This means that $(g^m)^k ne e$ for all $1 le k le n-1$, i.e. $n nmid mk$ for all $1 le k le n-1$.



If $gcd(n,m) = d > 1$ then, letting $m = da$ and $n = db$, the above condition becomes $b nmid ak$ for all $1 le k le n-1$. Since $d>1$, it follows that $b<n$, so if you choose $k=b$ you get $b mid ab$, which is contradicts the assumption that $n nmid mk$ for all $1 le k le n-1$. It follows that, necessarily, $gcd(n,m) = 1$.



Let us show that the condition $gcd(m,n) = 1$ is also sufficient for $g^m$ to be a generator. Assume there exist $2 le k le n-1$ with $(g^m)^k = e$. Since $gcd(m,n) = 1$, by Bézout's theorem there exist $s,t in Bbb Z$ such that $sm + tn = 1$, which implies $smk + tnk = k$, whence it follows that



$$e = e^s = (g^{mk})^s = g^{mks} = g^{k - tnk} = g^k (g^n)^{-tk} = g^k ,$$



so $g^k = e$, which contradicts the fact that $g$ is a generator.



We have discovered that in order for $g^m$ to be a generator, it is necessary and sufficient that $gcd(m,n)=1$, for $2 le m le n-1$. How many numbers coprime with $n$ do we have in ${2, 3, dots, n-1}$? By definition, $varphi(n)-1$, where $varphi$ is Euler's totient function. We have a "$-1$" because we start counting from $m=2$; taking into consideration that $g$ is a generator, too, and it corresponds to $m=1$, we get a total of $varphi(n)$ generators.






share|cite|improve this answer












Let $g$ be a generator of $G$. Let $g^m$ be another generator, with $2 le m le n-1$. This means that $(g^m)^k ne e$ for all $1 le k le n-1$, i.e. $n nmid mk$ for all $1 le k le n-1$.



If $gcd(n,m) = d > 1$ then, letting $m = da$ and $n = db$, the above condition becomes $b nmid ak$ for all $1 le k le n-1$. Since $d>1$, it follows that $b<n$, so if you choose $k=b$ you get $b mid ab$, which is contradicts the assumption that $n nmid mk$ for all $1 le k le n-1$. It follows that, necessarily, $gcd(n,m) = 1$.



Let us show that the condition $gcd(m,n) = 1$ is also sufficient for $g^m$ to be a generator. Assume there exist $2 le k le n-1$ with $(g^m)^k = e$. Since $gcd(m,n) = 1$, by Bézout's theorem there exist $s,t in Bbb Z$ such that $sm + tn = 1$, which implies $smk + tnk = k$, whence it follows that



$$e = e^s = (g^{mk})^s = g^{mks} = g^{k - tnk} = g^k (g^n)^{-tk} = g^k ,$$



so $g^k = e$, which contradicts the fact that $g$ is a generator.



We have discovered that in order for $g^m$ to be a generator, it is necessary and sufficient that $gcd(m,n)=1$, for $2 le m le n-1$. How many numbers coprime with $n$ do we have in ${2, 3, dots, n-1}$? By definition, $varphi(n)-1$, where $varphi$ is Euler's totient function. We have a "$-1$" because we start counting from $m=2$; taking into consideration that $g$ is a generator, too, and it corresponds to $m=1$, we get a total of $varphi(n)$ generators.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Feb 21 '17 at 20:39









Alex M.Alex M.

28k103058




28k103058












  • Alex M., what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03


















  • Alex M., what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03
















Alex M., what do you think of my proof please?
– BCLC
Aug 28 '18 at 6:03




Alex M., what do you think of my proof please?
– BCLC
Aug 28 '18 at 6:03











3














A cyclic group of order $n$ has exactly $varphi(n)$ generators where $varphi$ is Euler's totient function.



This is the number of $kin{0,ldots,n-1}$ such that:



$$gcd(k,n)=1.$$



You can find an explicit expression:



$$varphi(n)=nprod_{pmid n}left(1-frac 1pright).$$






share|cite|improve this answer





















  • E. Joseph, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03
















3














A cyclic group of order $n$ has exactly $varphi(n)$ generators where $varphi$ is Euler's totient function.



This is the number of $kin{0,ldots,n-1}$ such that:



$$gcd(k,n)=1.$$



You can find an explicit expression:



$$varphi(n)=nprod_{pmid n}left(1-frac 1pright).$$






share|cite|improve this answer





















  • E. Joseph, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03














3












3








3






A cyclic group of order $n$ has exactly $varphi(n)$ generators where $varphi$ is Euler's totient function.



This is the number of $kin{0,ldots,n-1}$ such that:



$$gcd(k,n)=1.$$



You can find an explicit expression:



$$varphi(n)=nprod_{pmid n}left(1-frac 1pright).$$






share|cite|improve this answer












A cyclic group of order $n$ has exactly $varphi(n)$ generators where $varphi$ is Euler's totient function.



This is the number of $kin{0,ldots,n-1}$ such that:



$$gcd(k,n)=1.$$



You can find an explicit expression:



$$varphi(n)=nprod_{pmid n}left(1-frac 1pright).$$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Feb 21 '17 at 19:49









E. JosephE. Joseph

11.6k82856




11.6k82856












  • E. Joseph, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03


















  • E. Joseph, what do you think of my proof please?
    – BCLC
    Aug 28 '18 at 6:03
















E. Joseph, what do you think of my proof please?
– BCLC
Aug 28 '18 at 6:03




E. Joseph, what do you think of my proof please?
– BCLC
Aug 28 '18 at 6:03











2














Suppose $g$ is a generator of $G$, then any element in $G$ may be written $g^b$. Now we only have to figure out which $b$'s make $g^b$ a generator.



If $g^b$ is a generator, then $(g^b)^n=g^{bn}=e$, and $$(g^b)^1neq e\(g^b)^2neq e\(g^b)^3neq e\dots\(g^b)^{n-1}neq e$$ This means that $b,n$ have no common factor, that is $gcd(b,n)=1$. So every $b$, for which $gcd(b,n)=1$, makes $g^b$ a generator of $G$. The number of generators is therefore $$phi(n)=|{kmid 1leq k< n,gcd(k,n)=1}|$$






share|cite|improve this answer





















  • 1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
    – ikoikoia
    Oct 30 '18 at 10:15












  • @ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
    – cansomeonehelpmeout
    Oct 30 '18 at 11:20


















2














Suppose $g$ is a generator of $G$, then any element in $G$ may be written $g^b$. Now we only have to figure out which $b$'s make $g^b$ a generator.



If $g^b$ is a generator, then $(g^b)^n=g^{bn}=e$, and $$(g^b)^1neq e\(g^b)^2neq e\(g^b)^3neq e\dots\(g^b)^{n-1}neq e$$ This means that $b,n$ have no common factor, that is $gcd(b,n)=1$. So every $b$, for which $gcd(b,n)=1$, makes $g^b$ a generator of $G$. The number of generators is therefore $$phi(n)=|{kmid 1leq k< n,gcd(k,n)=1}|$$






share|cite|improve this answer





















  • 1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
    – ikoikoia
    Oct 30 '18 at 10:15












  • @ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
    – cansomeonehelpmeout
    Oct 30 '18 at 11:20
















2












2








2






Suppose $g$ is a generator of $G$, then any element in $G$ may be written $g^b$. Now we only have to figure out which $b$'s make $g^b$ a generator.



If $g^b$ is a generator, then $(g^b)^n=g^{bn}=e$, and $$(g^b)^1neq e\(g^b)^2neq e\(g^b)^3neq e\dots\(g^b)^{n-1}neq e$$ This means that $b,n$ have no common factor, that is $gcd(b,n)=1$. So every $b$, for which $gcd(b,n)=1$, makes $g^b$ a generator of $G$. The number of generators is therefore $$phi(n)=|{kmid 1leq k< n,gcd(k,n)=1}|$$






share|cite|improve this answer












Suppose $g$ is a generator of $G$, then any element in $G$ may be written $g^b$. Now we only have to figure out which $b$'s make $g^b$ a generator.



If $g^b$ is a generator, then $(g^b)^n=g^{bn}=e$, and $$(g^b)^1neq e\(g^b)^2neq e\(g^b)^3neq e\dots\(g^b)^{n-1}neq e$$ This means that $b,n$ have no common factor, that is $gcd(b,n)=1$. So every $b$, for which $gcd(b,n)=1$, makes $g^b$ a generator of $G$. The number of generators is therefore $$phi(n)=|{kmid 1leq k< n,gcd(k,n)=1}|$$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Oct 8 '18 at 17:19









cansomeonehelpmeoutcansomeonehelpmeout

6,7573835




6,7573835












  • 1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
    – ikoikoia
    Oct 30 '18 at 10:15












  • @ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
    – cansomeonehelpmeout
    Oct 30 '18 at 11:20




















  • 1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
    – ikoikoia
    Oct 30 '18 at 10:15












  • @ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
    – cansomeonehelpmeout
    Oct 30 '18 at 11:20


















1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
– ikoikoia
Oct 30 '18 at 10:15






1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks!
– ikoikoia
Oct 30 '18 at 10:15














@ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
– cansomeonehelpmeout
Oct 30 '18 at 11:20






@ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $ainBbb Z_n$. 2. If $b,n$ had some common factor, say $d=gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $Bbb Z_n$, namely $g^b, (g^b)^2, dots, (g^b)^{n'}=e$
– cansomeonehelpmeout
Oct 30 '18 at 11:20




















draft saved

draft discarded




















































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.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • 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.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2155137%2fcyclic-group-generators-of-order-n%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

Plaza Victoria

Puebla de Zaragoza

Musa