Group Generators: Showing a^r is Generator of G

  • Thread starter Thread starter teleport
  • Start date Start date
  • Tags Tags
    Generators Group
Click For Summary

Homework Help Overview

The problem involves a finite cyclic group G of order n, with a generator a. The task is to demonstrate that a^r, where r is a non-zero integer relatively prime to n, is also a generator of G.

Discussion Character

  • Exploratory, Conceptual clarification, Mathematical reasoning

Approaches and Questions Raised

  • The original poster attempts to show that for any element b in G, there exists an integer m such that (a^r)^m = b. Some participants suggest solving the equation r*m = s mod n and question the necessity of understanding Z(n). Others discuss the implications of r being relatively prime to n and the existence of an integer t satisfying t*r = 1 mod n.

Discussion Status

The discussion is exploring various approaches to the problem, with participants providing hints and clarifications about the relationships between r, n, and the structure of the group G. There is no explicit consensus yet, but some productive lines of reasoning have emerged.

Contextual Notes

Participants note that the original poster has not yet covered Z(n) in their studies, which may impact their understanding of the problem. There is also a consideration of the need to show that the period of a^r is n to confirm that it generates the entire group G.

teleport
Messages
240
Reaction score
0

Homework Statement



Let G be a finite cyclic group of order n. Let a be a generator. Let r be an integer, not zero, and relatively prime to n.

a)Show that a^r is also a generator of G.


Homework Equations





The Attempt at a Solution



For the first one I need to show that for any element b in G there exists some integer m s.t. (a^r)^m = b. I have no idea what to do. The great thing about this is that I will be tested on this tomorrow. Ha, you get it. Pleast try to answer as soon as possible. Thanks for any help.
 
Physics news on Phys.org
b=a^s, since a generates G. Can you solve r*m=s mod n, where r is relatively prime to n. Hint: does r have an inverse in Z(n)?
 
Thanks. But we haven't gotten around Z(n) yet. Don't know what that is. Not sure I'm following you either. Does the solution require knowledge of Z(n) or is there any other way around it? Thanks again.
 
You need to know that if r and n are relatively prime, then there is an integer t such that t*r=1 mod n.
 
oh, so now we multiply both sides of the eqn by s:

s*t*r = s mod n

and let m = s*t. Now we get a^(str) = a^(mr) = a^(s mod n) = a^s.

We have shown for any b in G s.t. b = a^s for some s, b = a^rm for some m.

Is that good?
 
Wouldn't we have to show also that the period of a^r is n, to make sure that a^r is not generating something with greater size than G?
 
Oh, because a^r is an element of G, it can only generate subgroups which cannot have greater order than n. ok its clear. Thanks a lot.
 

Similar threads

  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 15 ·
Replies
15
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K