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?
Suppose ord(a) = 6. Then
What are the generators of <a>? 1 obviously isn't (<1> = {1}). a obviously is. What about
.
Thus
Do the same examination for and hopefully you'll see/understand the relationship
between relative primeness of s and n for , and whether is a fellow generator of <a>.
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 |a^{k}|?
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 a^{k} is t.
clearly (a^{k})^{t} = a^{kt} = a^{n} = e, since |a| = n.
now suppose (a^{k})^{s} = e, for some 0 < s < t.
thus a^{ks} = 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 a^{0} = 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.
now (a^{k})^{v} = (a^{du})^{v} = a^{duv} = a^{dvu} = (a^{dv})^{u} = (a^{n})^{u} = e^{u} = e.
so |a^{k}| divides v (= n/(gcd(k,n)), at the very least.
suppose (a^{k})^{r} = e, with 0 < r < v.
this mean a^{kr} = 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 |a^{k}| = v = n/(gcd(k,n)).
now, a^{k} is a generator for <a> if a^{k} 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> (a^{0} = a^{n} = 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,a^{2},....a^{11}}.
clearly |a^{1}| = |a| = 12, and |a^{0}| = |e| = 1 (and 12/(gcd(0,12)) = 12/12 = 1).
how about the order of a^{2}? well it's pretty obvious |a^{2}| = 6 (because 2 goes evenly into 12).
ok, what about a^{10}. let's do this two ways:
first we compute powers of a^{10} until we get the identity:
(a^{10})^{2} = a^{20} = (a^{12})(a^{8}) = ea^{8} = a^{8}
(a^{10})^{3} = a^{30} = (a^{24})(a^{6}) = (a^{12})^{2}(a^{6}) = e^{2}a^{6} = a^{6}
(a^{10})^{4} = a^{40} = (a^{36})(a^{4}) = a^{4} (i hope you understand the short-cut i took here)
(a^{10})^{5} = a^{50} = (a^{48})(a^{2}) = a^{2}
(a^{10})^{6} = a^{60} = (a^{12})^{5} = e^{5} = e
so |a^{10}| = 6.
using our formula:
gcd(10,12) = 2, so |a^{10}| = 12/2 = 6. that's...easier to do, right?
it should hopefully be clear by now that the generators of <a> are:
a,a^{5},a^{7},a^{11}, so we have 4 of them, and:
φ(12) = φ(4)φ(3) = φ(2^{2})φ(3) = (2-1)2^{1}(3-1)3^{0} = (1)(2)(2)(1) = 4, what do you know!