Transcript cyclic_groups3

Cyclic Groups
Part 2
Review
• Definition: G is cyclic if G = <a> for some a in
G.
• Thm 4.1
• If |a| = ∞, ai=aj iff i =j
• If |a| = n, ai=aj iff n| i – j
• <a> = {a, a2, … an-1,e}
• Cor 1: |a| = |<a>|
• Cor 2: ak = e implies |a| | k
Review (con't)
• Thm 4.2 If |a| = n, then
• <ak> = <agcd(n,k)>
• |ak| = n/gcd(n,k)
• Proved first part last time.
Proof of 4.2
• To prove the |ak| = n/gcd(n,k) , we begin
with a little lemma.
• Prove: If d | n = |a|, then |ad| = n/d.
• Proof: Let n = dq. Then e = an = (ad)q.
So |ad| ≤ q.
If 0< i < q, then 0 < di < dq = n = |a|
so (ad)i ≠ e
Hence, |ad| = q which is n/d as required.
Proof that |ak| = n/gcd(n,k)
• Now let d = gcd(n,k). We have
|ak| = |<ak>|
by 4.1 cor 1
= |<ad>|
by part 1
= |ad|
by 4.1 cor 1
= n/d
by our lemma.
• This concludes the proof of 4.2.
Example
• Suppose G = <a> with |a| = 30.
Find |a21| and <a21>.
• By Thm 4.2, |a21| = 30/gcd(30,21) = 10
• Also <a21> = <a3>
= {a3, a6, a9, a12,a15, a18, a21, a24, a27, e}
Corollaries to Theorem 4.2
1.
In a finite cyclic group, the order of an
element divides the order of the
group.
2. Let |a| = n in any group. Then
a) <ai> = <aj> iff gcd(n,i) = gcd(n,j)
b) |ai| = |aj| iff gcd(n,i) = gcd(n,j)
More corollaries to 4.2
3. Let |a| = n.
Then <ai> = aj iff gcd(n,i) = gcd(n,j)
4. An integer k in Zn is a generator of Zn
iff gcd(n,j) = 1
Example
• Find all the generators of U(50) = <3>.
• |U(50)| = 20
• The numbers relatively prime to 20 are
1, 3, 7, 9, 11, 13, 17, 19
The generators of U(50) are therefore
31, 33, 37, 39, 311, 313, 317, 319
i.e. 3, 27, 37, 33, 47, 23, 13, 17
Example
• In D8, List all generators of <R45º>
• |R45| = 8
• The numbers relatively prime to 8 are
1, 3, 5, 7
The generators are
R45, R453, R455, R457
i.e. R45, R135, R225, R315
Fundamental Theorem of
Cyclic Groups
a) Every subgroup of a cyclic group is
cyclic.
b) If |a| = n, then the order of any
subgroup of <a> is a divisor of n
c) For each positive divisor k of n, the
group <a> has exactly one subgroup
of order k, namely <an/k>
(a) Subgroups are cyclic
• Proof: Let G = <a> and suppose H ≤ G. If H
is trivial, then H is cyclic.
Suppose H is not trivial.
Let m be the smallest positive integer with am
in H. (Does m exist?) ________
By closure, <am> is contained in H.
We claim that H = <am>. To see this,
choose any b = ak in H. There exist integers
q,r with 0 ≤ r < m such that
ak = aqm + r (Why?) ___________
• Since b = ak = aqma r, we have
ar = (am)-q b
Since b and am are in H, so is ar.
But r < m (the smallest power of a in H)
so r = 0.
Hence b = (am)q and b is in H.
It follows that H = <am> as required.
(b) |H| is a divisor of |a|
• Proof: Given |<a>| = n and H ≤ <a>.
We showed H = <am> where m is the
smallest positive integer with am in H.
Now e = an is in H, so as we just
showed, n = mq for some q.
Now |am| = q is a divisor of n as
required.
(c) Exactly one subgroup for
each divisor k of n
• (Existence) Given |<a>| = n. Let k | n.
Say n = kq. Note that gcd(n,q) = q
So |aq| = n/gcd(n,q) = n/q = k.
Hence there exists a subgroup of order
k, namely <an/q>
(c) Con't.
• (Uniqueness) Let H be any subgroup of <a>
with order k. We claim H = <an/k>
From (a), H = <am> for some m.
From (b), m | n so gcd(n,m) = m.
So k = |am| = n/gcd(n,m) by 4.2
= n/m
Hence m = n/k
So H = <an/k> as required.
Subgroups of Zn
• For each positive divisor k of n, the set
<n/k> is the unique subgroup of Zn of
order k. Moreover, these are the only
subgroups of Zn.
Euler Phi Function
• (n) = the number of relatively prime
positive numbers < n
• |U(n)| = (n)
• (n) = n*(1-1/p1)(1-1/p2)…
where p1, p2 … are prime divisors of n
Theorem 4.4
• If d is a positive divisor of n, the number of
elements of order d in a cyclic group of order
n is (d).
• Proof: By the FTCG, there is a unique
subgroup H of order d.
Clearly, |a| = d iff a generates H.
Choose any generator b. By cor 3 of 4.2,
bk generates H iff gcd(k,d) = 1.
Hence the number of generators of H is (d).
Example
• How many elements of order 8 in Z16?
(8) = 8(1-1/2) = 4
• Find them:
In Z16, |2| = 16/2 = 8.
Generators of <2> are
2{1,3,5,7} = {2,6,10,14}
• These are all elements of order 8 in Z16
Another Example
• How many elements of order 8 in Z800?
• (8) = 8(1-1/2) = 4
• Find them:
In Z800 800/8 = 100 has order 8
The generators of <100> are
100{1,3,5,7} = {100, 300, 500, 700}
• These are all elements of order 8 in Z800
What can we say about all
finite groups?
• Theorem 4.5 In a finite group, the number of
elements of order d is a multiple of (d).
• Proof: Let G be a finite group with n elements
of order d.
Let b be the number of cyclic subgroups G
with order d.
Each element of order d belongs to exactly
one cyclic subgroup of order d.
Thus n = b•(d).
Final Example
• In U(20) Find the number of elements of
order 4
• U(20) = {1, 3, 7, 9, 11, 13, 17, 19}
<3> = {3, 9, 7, 1} and
<13> = {13, 9, 7, 1}
• U(20) is not cyclic.
• Elements of order 4 are 3, 7, 13, 9.
• n = 2•(4) = 4