# Thread: Generators of Cyclic Groups

1. ## Generators of Cyclic Groups

Let a have order n, and prove <a> has phi(n) different generators.

I am not sure how to relate phi(n) and a as a generated group?

2. ## Re: Generators of Cyclic Groups

Suppose ord(a) = 6. Then $\displaystyle <a> = \{1, a, a^2, a^3, a^4, a^5 \}.$

What are the generators of <a>? 1 obviously isn't (<1> = {1}). a obviously is. What about $\displaystyle a^2 \ ?$

$\displaystyle <a^2> = \{ (a^2)^0 = 1, (a^2)^1 = a^2, (a^2)^2 = a^4, (a^2)^3 = a^6 = 1 \} = \{1, a^2, a^4 \}$.

Thus $\displaystyle <a^2> \ \ne \ <a>, \text{ and so } a^2 \text{ doesn't generate } <a>.$

Do the same examination for $\displaystyle a^3, a^4, \text{ and } a^5,$ and hopefully you'll see/understand the relationship

between relative primeness of s and n for $\displaystyle a^s$, and whether $\displaystyle a^s$ is a fellow generator of <a>.

3. ## Re: Generators of Cyclic Groups

I've written the proof below, but if you want a hint, use the fact that if gcd(a, b) = d, then d = na + mb , for integers n, m
Spoiler:

If n = 1, then it is easy to see that $\displaystyle \phi(1) = 1$ your group has 1 generator. Now take $\displaystyle n > 1$ Take A = {$\displaystyle x | 0 < x < n, gcd(x, n) = 1$ and x is an integer } so basically $\displaystyle |A| = \phi(n)$ . Now take $\displaystyle x \in A$, if we pulled x = 1, then we can easily see $\displaystyle a^x = a^1$ is a generattor, now take $\displaystyle x \in A, x \not = 1$, so, since gcd(m, n) can be written in the form gcd(m, n) = pm + qn , where p, q are integers, we see that $\displaystyle gcd(x, n) = 1$ so $\displaystyle 1 = xp + nq$ where p and q are integers, and so $\displaystyle a^1 = a^{xp + nq} = a^{xp} \dot a^{nq}$ which equals $\displaystyle a^1 = a^{xp} \dot e$, now since we assumed$\displaystyle 1 < x < n$, we can say $\displaystyle a^x \not = a^1$ so since $\displaystyle (a^{x})^p = a^{xp} = a$ $\displaystyle a^x$ is also a generator of the group (if you take any element in <a> and by raising it to powers, get a as a result after some power, that initial element is a generator of the whole group), thus $\displaystyle a^x$ where $\displaystyle x \in A$ are unique elements of the group $\displaystyle <a>$, and since a raised to a power from A gives us a unique generator, so $\displaystyle |A| = \phi(n)$ is the number of generators for <a>

4. ## Re: Generators of Cyclic Groups

first of all, this is actually a statement about cyclic groups (<a> is cyclic, with generator a).

so one might ask: for a given k, what is |ak|?

if |a| = n, i claim it is: n/(gcd(k,n)).

let's look at a "nice case" first: suppose k|n, so n = kt, for some positive integer t.

i claim in this case, the order of ak is t.

clearly (ak)t = akt = an = e, since |a| = n.

now suppose (ak)s = e, for some 0 < s < t.

thus aks = e, where 0 < ks < kt = n, contradicting that |a| = n.

note this still adheres to our formula above, because when n = kt, gcd(k,n) = gcd(k,kt) = k(gcd(1,t)) = k(1) = k,

so n/(gcd(k,n)) = n/k = kt/k = t.

another "nice case": suppose k = 0, then a0 = e, and n/(gcd(0,n)) = n/n = 1 (and indeed the identity always has order 1).

so now, suppose gcd(k,n) = d, where d < n. thus k = du, and n = dv for some positive integers u and v, with gcd(u,v) = 1.

so n/(gcd(k,n)) = dv/d = v.

so |ak| divides v (= n/(gcd(k,n)), at the very least.

suppose (ak)r = e, with 0 < r < v.

this mean akr = e, so n divides kr. we can write this as: kr = nw (for some integer w).

so dur = dvw, thus: ur = vw.

now u divides ur, and gcd(u,v) = 1, so u|w. so w = ux, for some positive integer x (i DO apologize for using so many letters).

so now from kr = nw, we have:

dur = dvux, that is:

r = vx, which can't be possible, since 0 < r < v (vx ≥ v since x is positive).

so no such r exists, so |ak| = v = n/(gcd(k,n)).

now, ak is a generator for <a> if ak has order n, so that n/(gcd(k,n)) = n, in which case gcd(k,n) must be 1.

by definition, φ(n) = {k in Z: 0 < k < n and gcd(k,n) = 1}, so we see we have φ(n) generators for <a> (a0 = an = e is never a generator unless n = 1).

phew!

now, all this might seem a bit abstract, so it helps to look at a concrete example:

let |a| = 12. so <a> = {e,a,a2,....a11}.

clearly |a1| = |a| = 12, and |a0| = |e| = 1 (and 12/(gcd(0,12)) = 12/12 = 1).

how about the order of a2? well it's pretty obvious |a2| = 6 (because 2 goes evenly into 12).

ok, what about a10. let's do this two ways:

first we compute powers of a10 until we get the identity:

(a10)2 = a20 = (a12)(a8) = ea8 = a8
(a10)3 = a30 = (a24)(a6) = (a12)2(a6) = e2a6 = a6
(a10)4 = a40 = (a36)(a4) = a4 (i hope you understand the short-cut i took here)
(a10)5 = a50 = (a48)(a2) = a2
(a10)6 = a60 = (a12)5 = e5 = e

so |a10| = 6.

using our formula:

gcd(10,12) = 2, so |a10| = 12/2 = 6. that's...easier to do, right?

it should hopefully be clear by now that the generators of <a> are:

a,a5,a7,a11, so we have 4 of them, and:

φ(12) = φ(4)φ(3) = φ(22)φ(3) = (2-1)21(3-1)30 = (1)(2)(2)(1) = 4, what do you know!