mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2010-06-24, 14:04   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default 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.
davar55 is offline   Reply With Quote
Old 2010-06-30, 08:07   #2
proximity4
 

3·1,031 Posts
Default

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.
  Reply With Quote
Old 2010-06-30, 19:55   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

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?
davar55 is offline   Reply With Quote
Old 2010-12-05, 23:10   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

I'd especially like to know if the redundancy in the proof
could be simplified or eliminated.
davar55 is offline   Reply With Quote
Old 2010-12-08, 19:41   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

Quote:
I'd especially like to know if the redundancy in the proof
could be simplified or eliminated.
That is, if there's anyone here interested in math. :)
davar55 is offline   Reply With Quote
Old 2010-12-08, 20:30   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101100010012 Posts
Default

Quote:
Originally Posted by davar55 View Post
That is, if there's anyone here interested in math. :)
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).
R. Gerbicz is offline   Reply With Quote
Old 2010-12-11, 15:42   #7
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

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?
davar55 is offline   Reply With Quote
Old 2010-12-19, 18:27   #8
Unregistered
 

22·3·11·37 Posts
Default

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.
  Reply With Quote
Old 2010-12-20, 12:56   #9
davar55
 
davar55's Avatar
 
May 2004
New York City

101468 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2011-01-16, 05:34   #10
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2011-01-16, 20:51   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
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
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cyclic fields with class number h carpetpool Abstract Algebra & Algebraic Number Theory 0 2018-01-30 06:10
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic Nick Number Theory Discussion Group 0 2017-01-07 13:15
What is this group? wpolly Math 1 2008-06-09 12:14
checking cyclic group belongingness of an element vector Math 9 2007-12-02 10:26
Do I need group theory for this? Orgasmic Troll Math 1 2005-01-21 12:50

All times are UTC. The time now is 16:56.

Sat Nov 28 16:56:19 UTC 2020 up 79 days, 14:07, 4 users, load averages: 1.19, 1.24, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.