 mersenneforum.org Cyclic Group Problem
 Register FAQ Search Today's Posts Mark Forums Read  2010-06-24, 14:04 #1 davar55   May 2004 New York City 5·7·112 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 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.   2010-06-30, 08:07 #2 proximity4   23×3×89 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.  2010-06-30, 19:55 #3 davar55   May 2004 New York City 102138 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?   2010-12-05, 23:10 #4 davar55   May 2004 New York City 10000100010112 Posts I'd especially like to know if the redundancy in the proof could be simplified or eliminated.   2010-12-08, 19:41   #5
davar55

May 2004
New York City

5×7×112 Posts 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. :)   2010-12-08, 20:30   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

17×97 Posts Quote:
 Originally Posted by davar55 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).   2010-12-11, 15:42 #7 davar55   May 2004 New York City 423510 Posts 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?   2010-12-19, 18:27 #8 Unregistered   17·587 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.  2010-12-20, 12:56 #9 davar55   May 2004 New York City 5·7·112 Posts 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.   2011-01-16, 05:34 #10 davar55   May 2004 New York City 5×7×112 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.   2011-01-16, 20:51   #11
wblipp

"William"
May 2003
Near Grandkid

45078 Posts Quote:
 Originally Posted by davar55 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 0 2018-01-30 06:10 Nick Number Theory Discussion Group 0 2017-01-07 13:15 wpolly Math 1 2008-06-09 12:14 vector Math 9 2007-12-02 10:26 Orgasmic Troll Math 1 2005-01-21 12:50

All times are UTC. The time now is 22:28.

Mon Sep 25 22:28:19 UTC 2023 up 12 days, 20:10, 0 users, load averages: 1.23, 1.17, 1.18