1. Let G = <a> be a finite cyclic group of order n. Prove that G=<a^k> if and only if (k,n)=1. (NOTE: the notation (k,n) means greatest common divisor, or gcd(k,n).)
Using the above result conclude that if G is a finite cyclic cyclic group of order n, then G has exactly ϕ(n) number of generators (Where ϕ(n) is Euler's function, which is the number of positive integers less than n and relatively prime to n)
2. Let G = <a> be an infinite cyclic group. Prove that G=<a^k> if and only if k=1 or k=-1.
Using the above result, conclude that if G is an infinite cyclic group then G has exactly two generators.
3. Prove that a group G has no proper subgroups (that is, subgroups other than G and {e}) if and only if G is a cyclic group of prime order.
4. Prove that for any prime p, (p - 1)!≡-1(mod p)
(Hint: Think about the elements of group U_p. Find which elements are of order 2) (U_n = {a_n is and element of (Z_n)^* : (a,n)=1})
Questions formatted a little nicer: http://i.imgur.com/wX2Lu.png
Any hints? I'm not looking for straight solutions, but if you give them to me, I'll certainly appreciate it.
Answers & Comments
Verified answer
1a) If G = <a^k>, then a ∈ <a^k> so that a = a^(kt) for some integer t.
==> a^(kt-1) = 1. Thus, n|(kt - 1) ==> nr = kt - 1 for some integer r.
Thus, 1 is a Z-linear combination of k and n ==> gcd(k, n) = 1.
Conversely, if gcd(k, n) = 1 we have kr + ns = 1 for some integers r and s.
Hence, a = a^(kr + ns) = a^(kr) a^(ns) = a^(kr) * 1 = a^(kr) ∈ <a^k>.
Therefore, every power of a also is in <a^k>, and so G = <a^k>.
b) By part (a), a^k is a generator of G <==> gcd(k, n) = 1. The number of such k is given by the Euler phi function. Thus, there are ϕ(n) such generators.
----------------------------
2a) If k = 1, this is obvious. If k = -1, then since a^(-1) ∈ <a^(-1)>, so is [a^(-1)]^(-1) = a (and vice versa). Thus, <a^(-1)> = <a> = G.
Conversely, suppose that G = <a^k>. Then (a^k)^r = a^(kr) = a for some integer r.
==> a^(kr-1) = 1. However, a has infinite order. Thus, kr = 1 ==> k (and r) = -1 or 1.
b) From part (a), G only has two generators a and a^(-1).
----------------------------
3) If G is cyclic of prime order, then G has no nontrivial proper subgroups, since every nontrivial element of G is a generator of G (by the first question).
Conversely, suppose that G has no nontrivial proper subgroups.
Let g ∈ G different from e. (If there is no such element, then G = {e} and G is cyclic. I suppose this should be included as a cyclic group of prime order in this question.)
Consider the set S = {g^n|n = 1, 2, 3, ...} Since this is not {e}, it must be G. Hence G is cyclic with generator g. G can't be of infinite order, because <g^2> is a proper subgroup of G = <g>. If G is of finite order and not cyclic, then G has a subgroup having order 1 < d < n, where d|n. Hence, G must be of prime order.
---------------------------
4) If p = 2, this is trivial. Hereafter, assume p is odd. Since p is prime, then each of {1, 2, ..., p-1} is relatively prime to p. So for each of these integers a there exists an integer b such that ab = 1 (mod p).
Since p is prime, a = b <==> if a = 1 or p-1 (these are the only elements having order dividing 2). Ignoring 1 and p-1, then the others can be grouped into pairs whose product is 1.
Therefore, 2 * 3 * 4 * ... * (p-2) = (p-2)! = 1 (mod p).
Multiplying both sides by p-1 = -1 (mod p) yields (p - 1)! = -1 (mod p).
---------------------------
I hope this helps!
It is easy to shows that there are at least m solutions. if a is a generator, then y=a^(n/m) has order m, so all powers of y are in the order m group generated by y and solve the equation x^m=1. But you also have to show that there are no more than m solutions. If you already know that there is only one subgroup of order m then use that fact. You may have proved in class that all subgroups of G are cyclic and there is exactly one such for every order m dividing n.