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 co-prime to n.

First, we know g^n = 1, and the group G = { 1,g,g^2,...,g^(n-1) }.

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 co-prime to n if and only if d = 1 (by definition)

Suppose d = 1 (so r and n are co-prime).
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 co-prime).
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.

Imagine the cyclic group on a [URL="http://www.physicsforums.com/library.php?do=view_item&itemid=56"][COLOR=#0000ff]circle[/COLOR][/URL] -- 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.

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?

I'd especially like to know if the redundancy in the proof
could be simplified or eliminated.

[quote]I'd especially like to know if the redundancy in the proof
could be simplified or eliminated.[/quote]

That is, if there's anyone here interested in math. :)

[QUOTE=davar55;240774]That is, if there's anyone here interested in math. :)[/QUOTE]

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^((k-l)*r)=1, so (k-l)*r is divisible by n, so: n|(k-l)*r, from this: n/gcd(n,r)|(k-l)*r/gcd(n,r), but here n/gcd(n,r) and r/gcd(n,r) are relative prime, so n/gcd(n,r)|k-l. It means that the (cyclic) subgroup has got size of n/gcd(n,r).

Is an all-on-one-long-line 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 book-ready. Any comments there?

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.

Perhaps someone would like to post a similar-veined pet proof
of some result/theorem (a short one, preferably) for comparison
of structure/format/styles.

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.

[QUOTE=davar55;246684]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.[/QUOTE]

Are you sure you want to keep trying to defend the "theorems are innumerable" claim? I think you should give it up and claim you were really speaking informally and meant something like "too many to grasp."

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