Mixing
Group Theory: Proving if G=, |G|=r, then G'==G provided a is coprime to r.
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
So this is my question:
Let G be the cyclic group generated by the element x. ie. G = < x > = 1, x, x^2, x^3...x^(r-1)
Now, |G|=r.
Prove that G'= < x^a > = G if a and r are coprime. (ie. the cyclic generated by x^a is equal to the cyclic group generated by x)
I get the intuition behind it. For instance, if a and r wasn't coprime, the subgroup generated by x^a would not generate any new elements once it goes back to the identity.
On the other hand, if a and r was coprime (ie. r=30 and a=7), then < x^7 > would be able to generate every single element of the group.
This is a lemma that I generated for myself to solve this question. I'm not sure if this is a well-established proof in math and I couldn't find any results on Google.
Lemma: 2 coprime numbers do not divide.
Let a and b be coprime.
a, b can be expressed as a product of some prime factorization.
a= p(1)^a(1)*p(2)^a(2)...
b= p'(1)^a'(1)*p'(2)^a'(2)...
p(x) does not equal p'(x) as if it does, it would mean that we have found a factor p(x) which divides both numbers. Because all primes used in the prime factorization of a and b are different, a does not divide b and vice versa.
The problem is that I don't know how to prove the above question vigorously. I was thinking of using the Lagrange's Theorem, and arguing that |< x >| must divide |< x^a >|. So if a and r weren't coprime, then |< x >| would divide |< x^a >| and so < x^a > would be a subgroup of < x >.
On the other hand, if a and r were coprime, then if we'd assume that < x^a > cannot contain all elements of < x >, then < x^a > would be a proper subgroup of < x >. If this subgroup exists, let's call its order r'. But r does not divide r'! So we have a contradiction and thus < x^a > cannot be a proper subgroup of < x >. Thus < x^a > = < x >, ie G'=G!
I'm not sure if I'm expressing myself very clearly here. Basically, I'm trying to show if you pick an arbitrary element from a cyclic group, and generate the group from it, you will either get a subgroup of the cyclic group or the entire group again. For a is coprime to r, there is no way in hell you're going to get a proper subgroup of order a as I've established that r does not divide a. Thus x^a must generate the entire group.
If there is a simpler way to prove it, please let me know. And also, I would be grateful if someone with a solid understanding of group theory critiques my proof.
group-theory
asked Jul 25 at 13:14
Yip Jung Hon
18011
add a comment |Â
up vote
2
down vote
favorite
So this is my question:
Let G be the cyclic group generated by the element x. ie. G = < x > = 1, x, x^2, x^3...x^(r-1)
Now, |G|=r.
Prove that G'= < x^a > = G if a and r are coprime. (ie. the cyclic generated by x^a is equal to the cyclic group generated by x)
I get the intuition behind it. For instance, if a and r wasn't coprime, the subgroup generated by x^a would not generate any new elements once it goes back to the identity.
On the other hand, if a and r was coprime (ie. r=30 and a=7), then < x^7 > would be able to generate every single element of the group.
This is a lemma that I generated for myself to solve this question. I'm not sure if this is a well-established proof in math and I couldn't find any results on Google.
Lemma: 2 coprime numbers do not divide.
Let a and b be coprime.
a, b can be expressed as a product of some prime factorization.
a= p(1)^a(1)*p(2)^a(2)...
b= p'(1)^a'(1)*p'(2)^a'(2)...
p(x) does not equal p'(x) as if it does, it would mean that we have found a factor p(x) which divides both numbers. Because all primes used in the prime factorization of a and b are different, a does not divide b and vice versa.
The problem is that I don't know how to prove the above question vigorously. I was thinking of using the Lagrange's Theorem, and arguing that |< x >| must divide |< x^a >|. So if a and r weren't coprime, then |< x >| would divide |< x^a >| and so < x^a > would be a subgroup of < x >.
On the other hand, if a and r were coprime, then if we'd assume that < x^a > cannot contain all elements of < x >, then < x^a > would be a proper subgroup of < x >. If this subgroup exists, let's call its order r'. But r does not divide r'! So we have a contradiction and thus < x^a > cannot be a proper subgroup of < x >. Thus < x^a > = < x >, ie G'=G!
I'm not sure if I'm expressing myself very clearly here. Basically, I'm trying to show if you pick an arbitrary element from a cyclic group, and generate the group from it, you will either get a subgroup of the cyclic group or the entire group again. For a is coprime to r, there is no way in hell you're going to get a proper subgroup of order a as I've established that r does not divide a. Thus x^a must generate the entire group.
If there is a simpler way to prove it, please let me know. And also, I would be grateful if someone with a solid understanding of group theory critiques my proof.
group-theory
asked Jul 25 at 13:14
Yip Jung Hon
18011
1
That coprime numbers do not divide, is kinda the definition of beeing coprime.
– Cornman
Jul 25 at 13:19
Well...haha thanks! I'm not that familiar with the concept of coprime numbers.
– Yip Jung Hon
Jul 25 at 13:22
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
So this is my question:
Let G be the cyclic group generated by the element x. ie. G = < x > = 1, x, x^2, x^3...x^(r-1)
Now, |G|=r.
Prove that G'= < x^a > = G if a and r are coprime. (ie. the cyclic generated by x^a is equal to the cyclic group generated by x)
I get the intuition behind it. For instance, if a and r wasn't coprime, the subgroup generated by x^a would not generate any new elements once it goes back to the identity.
On the other hand, if a and r was coprime (ie. r=30 and a=7), then < x^7 > would be able to generate every single element of the group.
This is a lemma that I generated for myself to solve this question. I'm not sure if this is a well-established proof in math and I couldn't find any results on Google.
Lemma: 2 coprime numbers do not divide.
Let a and b be coprime.
a, b can be expressed as a product of some prime factorization.
a= p(1)^a(1)*p(2)^a(2)...
b= p'(1)^a'(1)*p'(2)^a'(2)...
p(x) does not equal p'(x) as if it does, it would mean that we have found a factor p(x) which divides both numbers. Because all primes used in the prime factorization of a and b are different, a does not divide b and vice versa.
The problem is that I don't know how to prove the above question vigorously. I was thinking of using the Lagrange's Theorem, and arguing that |< x >| must divide |< x^a >|. So if a and r weren't coprime, then |< x >| would divide |< x^a >| and so < x^a > would be a subgroup of < x >.
On the other hand, if a and r were coprime, then if we'd assume that < x^a > cannot contain all elements of < x >, then < x^a > would be a proper subgroup of < x >. If this subgroup exists, let's call its order r'. But r does not divide r'! So we have a contradiction and thus < x^a > cannot be a proper subgroup of < x >. Thus < x^a > = < x >, ie G'=G!
I'm not sure if I'm expressing myself very clearly here. Basically, I'm trying to show if you pick an arbitrary element from a cyclic group, and generate the group from it, you will either get a subgroup of the cyclic group or the entire group again. For a is coprime to r, there is no way in hell you're going to get a proper subgroup of order a as I've established that r does not divide a. Thus x^a must generate the entire group.
If there is a simpler way to prove it, please let me know. And also, I would be grateful if someone with a solid understanding of group theory critiques my proof.
group-theory
asked Jul 25 at 13:14
Yip Jung Hon
18011
So this is my question:
Let G be the cyclic group generated by the element x. ie. G = < x > = 1, x, x^2, x^3...x^(r-1)
Now, |G|=r.
Prove that G'= < x^a > = G if a and r are coprime. (ie. the cyclic generated by x^a is equal to the cyclic group generated by x)
I get the intuition behind it. For instance, if a and r wasn't coprime, the subgroup generated by x^a would not generate any new elements once it goes back to the identity.
On the other hand, if a and r was coprime (ie. r=30 and a=7), then < x^7 > would be able to generate every single element of the group.
This is a lemma that I generated for myself to solve this question. I'm not sure if this is a well-established proof in math and I couldn't find any results on Google.
Lemma: 2 coprime numbers do not divide.
Let a and b be coprime.
a, b can be expressed as a product of some prime factorization.
a= p(1)^a(1)*p(2)^a(2)...
b= p'(1)^a'(1)*p'(2)^a'(2)...
p(x) does not equal p'(x) as if it does, it would mean that we have found a factor p(x) which divides both numbers. Because all primes used in the prime factorization of a and b are different, a does not divide b and vice versa.
The problem is that I don't know how to prove the above question vigorously. I was thinking of using the Lagrange's Theorem, and arguing that |< x >| must divide |< x^a >|. So if a and r weren't coprime, then |< x >| would divide |< x^a >| and so < x^a > would be a subgroup of < x >.
On the other hand, if a and r were coprime, then if we'd assume that < x^a > cannot contain all elements of < x >, then < x^a > would be a proper subgroup of < x >. If this subgroup exists, let's call its order r'. But r does not divide r'! So we have a contradiction and thus < x^a > cannot be a proper subgroup of < x >. Thus < x^a > = < x >, ie G'=G!
I'm not sure if I'm expressing myself very clearly here. Basically, I'm trying to show if you pick an arbitrary element from a cyclic group, and generate the group from it, you will either get a subgroup of the cyclic group or the entire group again. For a is coprime to r, there is no way in hell you're going to get a proper subgroup of order a as I've established that r does not divide a. Thus x^a must generate the entire group.
If there is a simpler way to prove it, please let me know. And also, I would be grateful if someone with a solid understanding of group theory critiques my proof.
group-theory
asked Jul 25 at 13:14
Yip Jung Hon
18011
asked Jul 25 at 13:14
Yip Jung Hon
18011
asked Jul 25 at 13:14
Yip Jung Hon
18011
asked Jul 25 at 13:14
Yip Jung Hon
18011
18011
1
That coprime numbers do not divide, is kinda the definition of beeing coprime.
– Cornman
Jul 25 at 13:19
Well...haha thanks! I'm not that familiar with the concept of coprime numbers.
– Yip Jung Hon
Jul 25 at 13:22
add a comment |Â
1
That coprime numbers do not divide, is kinda the definition of beeing coprime.
– Cornman
Jul 25 at 13:19
Well...haha thanks! I'm not that familiar with the concept of coprime numbers.
– Yip Jung Hon
Jul 25 at 13:22
1
1
That coprime numbers do not divide, is kinda the definition of beeing coprime.
– Cornman
Jul 25 at 13:19
That coprime numbers do not divide, is kinda the definition of beeing coprime.
– Cornman
Jul 25 at 13:19
Well...haha thanks! I'm not that familiar with the concept of coprime numbers.
– Yip Jung Hon
Jul 25 at 13:22
Well...haha thanks! I'm not that familiar with the concept of coprime numbers.
– Yip Jung Hon
Jul 25 at 13:22
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
SInce $r$ and $a$ are coprime, Bézout's lemma tells us that there are integers $m$ and $n$ such that $rm+an=1$. So$$x=x^1=x^rm+an=(x^a)^n.$$This proves that $xinlangle x^arangle$ and that therefore $Gsubsetlangle x^arangle$,
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
1
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
SInce $r$ and $a$ are coprime, Bézout's lemma tells us that there are integers $m$ and $n$ such that $rm+an=1$. So$$x=x^1=x^rm+an=(x^a)^n.$$This proves that $xinlangle x^arangle$ and that therefore $Gsubsetlangle x^arangle$,
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
1
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
 |Â
show 1 more comment
up vote
3
down vote
accepted
SInce $r$ and $a$ are coprime, Bézout's lemma tells us that there are integers $m$ and $n$ such that $rm+an=1$. So$$x=x^1=x^rm+an=(x^a)^n.$$This proves that $xinlangle x^arangle$ and that therefore $Gsubsetlangle x^arangle$,
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
1
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
 |Â
show 1 more comment
up vote
3
down vote
accepted
up vote
3
down vote
accepted
SInce $r$ and $a$ are coprime, Bézout's lemma tells us that there are integers $m$ and $n$ such that $rm+an=1$. So$$x=x^1=x^rm+an=(x^a)^n.$$This proves that $xinlangle x^arangle$ and that therefore $Gsubsetlangle x^arangle$,
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
SInce $r$ and $a$ are coprime, Bézout's lemma tells us that there are integers $m$ and $n$ such that $rm+an=1$. So$$x=x^1=x^rm+an=(x^a)^n.$$This proves that $xinlangle x^arangle$ and that therefore $Gsubsetlangle x^arangle$,
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
answered Jul 25 at 13:23
José Carlos Santos
113k1697176
113k1697176
1
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
 |Â
show 1 more comment
1
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
1
1
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
Wow...you're a wizard. But don't you have to prove both ways? ie. G⊂(x^a) and (x^a) ⊂ G?
– Yip Jung Hon
Jul 25 at 13:26
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I suppose that your talkang about the $subset$ sign. Yes, they're equal. The other inclusion is obvious.
– José Carlos Santos
Jul 25 at 13:27
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
I see I see. Thanks!
– Yip Jung Hon
Jul 25 at 13:28
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
@YipJungHon Any reason to mark my answer as accepted and then to un-mark it? Just curious.
– José Carlos Santos
Jul 25 at 14:24
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
Nah, don't take it personally. I realized that after marking your answer I wasn't getting any other replies, so I was wondering if StackExchange was not showing a resolved question to the wider community.
– Yip Jung Hon
Jul 25 at 14:47
 |Â
show 1 more comment
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862398%2fgroup-theory-proving-if-g-x-g-r-then-g-xa-g-provided-a-is-coprime-to%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
That coprime numbers do not divide, is kinda the definition of beeing coprime.
– Cornman
Jul 25 at 13:19
Well...haha thanks! I'm not that familiar with the concept of coprime numbers.
– Yip Jung Hon
Jul 25 at 13:22