20100624, 14:04  #1 
May 2004
New York City
2·2,099 Posts 
Cyclic Group Problem
The following problem appeared in the Math category
on Yahoo Answers. I gave the subsequent proof. Anyone care to critique it? Problem: Let G be cyclic group of order n, with generator g. Show that g^r (r being a integer) is a generator of G if and only if r is coprime to n." Proof: We want to prove: If G is a cyclic group of order n with generator g, then for any integer r, g^r is a generator of G if and only if r is coprime to n. First, we know g^n = 1, and the group G = { 1,g,g^2,...,g^(n1) }. Next use Euclidean Algorithm to find d = greatest common divisor (gcd) of r and n. This also gives a and b solving ar + bn = d. Then r is coprime to n if and only if d = 1 (by definition) Suppose d = 1 (so r and n are coprime). Then g = g^1 = g^(ar+bn) = g^(ar) * (g^n)^b = g^(ar) * 1^b = g^(ar) = (g^r)^a. This implies that g^r generates g hence g^2,g^3, etc. i.e. all of G. Conversely, suppose d > 1 (so r and n are NOT coprime). Then g^r generates { 1,g^r,g^2r,...g^(n/d  1)r) } which has at most n/d elements, n/d < n, because g^((n/d) * r) = (g^n)^(r/d) = 1. So it is not all of G. So d = 1 if and only if g^r generates G. 
20100630, 08:07  #2 
3·1,031 Posts 
Imagine the cyclic group on a circle  so they're actually cyclic. Generators are a certain spacing such that you get to every number before you go back to the beginning. As you've noted, a spacing of 1 is always possible. How about 2? It would go: 1, 3, 5 ... 29, 1, 3, ... so it would miss out the even numbers. 3? 1, 4, 7 ... 28, 1, 4, ... so it also misses things out. Try all the possibilities  it shouldn't take that long, and you should spot a pattern pretty soon. Try making a conjecture about what's happening. Try proving it.

20100630, 19:55  #3 
May 2004
New York City
2·2,099 Posts 
I think that qualifies as a prequel to the statement of the
problem I tried to solve. Makes it nicely clear that it's true, and my suggested proof is probably improvable (as opposed to inprovable :) ). Is there a simpler proof? 
20101205, 23:10  #4 
May 2004
New York City
2·2,099 Posts 
I'd especially like to know if the redundancy in the proof
could be simplified or eliminated. 
20101208, 19:41  #5  
May 2004
New York City
2·2,099 Posts 
Quote:


20101208, 20:30  #6 
"Robert Gerbicz"
Oct 2005
Hungary
10110001001_{2} Posts 
This problem is well known from Algebra 1. Its generalization: g^r generates a cyclic subgroup of size n/gcd(n,r):
proof: let k,l integers, then see when we get two equal element: g^(k*r)=g^(l*r) if and only if g^((kl)*r)=1, so (kl)*r is divisible by n, so: n(kl)*r, from this: n/gcd(n,r)(kl)*r/gcd(n,r), but here n/gcd(n,r) and r/gcd(n,r) are relative prime, so n/gcd(n,r)kl. It means that the (cyclic) subgroup has got size of n/gcd(n,r). 
20101211, 15:42  #7 
May 2004
New York City
2·2,099 Posts 
Is an allononelongline proof better than one with
vertical structure? It is interesting, but harder to read and comprehend. I'm still looking to improve my OP proof, to see if it could be bookready. Any comments there? 
20101219, 18:27  #8 
2^{2}·3·11·37 Posts 
Without going into symbolic logic or things
like the Incompleteness Theorem, I think there is a branch of math that's been sorely neglected: theory of proofs. That's why I posted this OP here  to get comments on the structure and clarity of mathematical proofs. 
20101220, 12:56  #9 
May 2004
New York City
10146_{8} Posts 
Perhaps someone would like to post a similarveined pet proof
of some result/theorem (a short one, preferably) for comparison of structure/format/styles. 
20110116, 05:34  #10 
May 2004
New York City
2×2,099 Posts 
I know proofs have been studied by such as Russel, Godel, etc,
but from a formal alphabet based counting perspective. I would suggest that natural proofs (i.e. real math) don't rely on the alphabet of symbols that just appear in some order and that's a proof. We use our eyes and brains to construct / understand a math proof. New symbolism, new constructs, new conceptual integrations, and the Gausses push math forward. 
20110116, 20:51  #11  
"William"
May 2003
New Haven
2^{2}×3^{2}×5×13 Posts 
Quote:
But if you are going to keep up this defense, you might pause to reflect that your claim, if true, would mean that there are theorems that cannot be stated in mathematical notation, even if extended to include English and Swahili. I didn't say "cannot be proven" and I didn't say "cannot be stated in finite length." William 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cyclic fields with class number h  carpetpool  Abstract Algebra & Algebraic Number Theory  0  20180130 06:10 
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic  Nick  Number Theory Discussion Group  0  20170107 13:15 
What is this group?  wpolly  Math  1  20080609 12:14 
checking cyclic group belongingness of an element  vector  Math  9  20071202 10:26 
Do I need group theory for this?  Orgasmic Troll  Math  1  20050121 12:50 