Repost from this link http://dogschool.tripod.com/cyclic.html
9. Cyclic Groups and Subgroups
Let's start with the number 1. We'll allow ourselves to add or subtract the number 1 to get to new numbers.
Question: what integers will we be able to reach by this process?
Answer: all of them.
To get to 17 simply add 1 16 times. To get to -42 simply subtract 1 43 times. The fact that the integers can be "built" by adding and subtracting 1 means that the additive group of integers is a
cyclic group.
Now let's look at the
Attayun-HOOT! group. The entire
Attayun-HOOT! group can be "built" from repeated applications of
R:
- R = (R1) = R
- R • R = (R2) = B
- R • R • R = (R3) = L
- R • R • R • R = (R4) = A
Groups that can be generated in their entirety from one member are called
cyclic groups. For infinite groups we have to clarify what we mean by "
generated from." For example in the additive group of Integers starting with 1 and adding it over and over to itself will never get a negative number nor the identity zero. Thus for a cyclic group we have the definition that all the elements may be generated from a single element
together with its inverse. For finite cyclic groups the addition of "
together with its inverse" is not needed. That statement probably should be stated as a theorem.
Theorem: If a finite group
G can be generated from one of its elements,
a together with its inverse
a-1 then it can be generated from
a alone.
Proof:
The strategy of the proof is to show that we can generate
a-1 from repeated applications of
a.
If
G is finite then the various powers of
a cannot all be distinct
[note that this would not necessarily follow if G is infinite]. Therefore for some two different positive integers,
j and
k
a • a • a • . . . • a • a(j times) = a • a • a • . . . • a • a(k times)
Assume without loss of generality that
j is greater than
k (Why can we do this?). Now if we multiply both sides of the equation by
a-1 • a-1 • a-1 • . . . • a-1 • a-1(k times) then we end up with
a • a • . . . • a(j-k times) = e
That means that
a-1 =
a • a • . . . • a(j-k-1 times).
Let's get away from all the " . . . " and "(j-k times)" by using exponential notation. Just as we do for multiplication of regular old numbers we can express repeated application of the group operation by a given element with exponential notation. So we'll agree that for an element
a of a group
G with operation •
- an means a • a • a • . . . • a (n times)
- a-n means a-1 • a-1 • a-1 • . . . • a-1 (n times)
- a0 means the identityb element e
We find that with this notation the basic law of exponents all work as in regular arithmetic namely
- am • an = am+n
- The inverse of an is a-n
- (am )n = amn
With this notation we mean that a
power of
a is
an where n is any integer: positive, negative or zero.
Cyclic Subgroups
If we pick some element
a from a group
G then we can consider the subset of all elements of
G that are powers of
a. This subset forms a subgroup of
Gand is called the
cyclic subgroup generated by a. If forms a subgroup since it is
- Closed. If you multiply powers of a you end up with powers of a
- Has the identity. a • a-1 = a0 = e
- Has inverses. The inverse of any product of a's is a similar product of a-1 's.
But this is the long way of proving subgrouphood. Let's use our theorem that says if
x and
y are in the subset implies that
x • y-1 is in the subset then the subset is a group. This is simple here. If
y is a power of
a then so is
y-1 and so, therefore, is
x • y-1 .
A few facts about cyclic groups and cyclic subgroups:
- Cyclic groups are Abelian.
- All groups of prime order are cyclic.
- The subgroup of a group G generated by a is the intersection of all subgroups of G containing a
- All infinite cyclic groups look like the additive group of integers.
[
Exercise: prove the first fact.]The second fact is a result of Lagrange's theorem. If
G is a group of prime order
p then take any non-identity element
a and look at the subgroup generated by it. The order of the subgroup must be a divisor of the order of
G (
Lagrange's Theorem) but since
G is of prime
p order the only divisors of
p are 1 and
p itself. Since
a isn't the identity the subgroup it generates must have more than one element. Therefore its order must be
pand it must be
Gitself --
G is cyclic. Furthermore since the choice of
a was only limited by its not being the identity it follows that
G can be generated by any of its elements other than
e.
The third fact is rather simple. Any subgroup containing
a contains
a-1 and therefore contains any products of
a's and
a-1 . Thus any subgroup containing
acontains the cyclic subgroup generated by
a. Since the cyclic subgroup generated by
a is a subroup the fact follows.
The fourth fact is poorly stated. "looks like" is not a well understood piece of mathematical terminology. We'll tighten things up as we go along.
Suppose
I is an infinite cyclic group generated by the element
a. Then any element of the group is of the form
an where n is an integer. Then the multiplication rule for this group ends up being
[am ] • [an ] = am + n
We can tighten up the notation of this group by letting the integer
n stand for the element
an . Then the "multiplication" rule for the group becomes
m • n = (m+n)
But this is just the behavior of the additive group of integers.
We have a one to one correspondence [
an corresponds to
n] which is preserved by the group operation [You can either perform the operation in one group and then find the corresponding element in the other or you can first find the corresponding elements in the other group and then perform the operation on them. The result is the same. And it works both ways. This is a group
isomorphism, a concept we have looked at but haven't rigorously defined yet.
Definition: Two groups
G and
H are
isomorphic if there exists a one-to-one relation
f :
G –> H between them such that for any
x and
y in
G,
f(
x) •
f(
y) =
f(
x * y). The one-to-one relation
f is called an
isomorphism. Thus two groups are said to be isomorphic if an isomorphism exists between them.
[
Note on my notation I've used two different symbols for the group operations in that last passage. • represents the group operation in
H and * represents the group operation in
G This was to emphasize that we are dealing with two different groups each with its own group operation.]
[
Exercise: show that the inverse relation works too. That is, show that if
g : H –>
G is the inverse of
f then for any
u and
v in
H it is true that
g(
u) *
g(
v) =
g(
u • v).]
One of the most common examples of a group isomorphism is found in the theory of logarithms. Let
f :
G –>H be the logarithm function and let
G be the group of positive real numbers under multiplication and let
H be the real numbers under addition. It turns out that
Log(x) + Log(y) = Log(xy)
This together with the fact that
Log is a one-to-one function (it has an inverse -- the exponential or "antilog" function) makes this a group isomorphism. This used to have great practical importance back in the days before pocket calculators. Long numerical calculations involving multiplication (and taking of roots and powers) could be simplified by doing addition of the
Logs of the numbers. In those days no scientist or engineer was far from his table of Logarithms.
The following are basic facts about group isomorphism:
If
f:
G –>
H is a group isomorphism then:
- If e is the identity in G then f(e) is the identity in H>.
- The inverse of f(a) in H is F(a-1).
Now we can restate our poorly stated fourth fact:4. All infinite cyclic groups are isomorphic to the additive group of integers.
The isomorphism is simply
an –>
n as we have already seen.
The main point about cyclic groups and isomorphism is that all finite cyclic groups of the same order are isomorphic. Thus there is only one cyclic group (up to isomorphism) of order, say, 6. If we let
a be a generator then the elements of the cyclic group of order 6 are
a,
a2,
a3,
a4,
a5, and
a6 =
e.
The canonical
example of a cyclic group of order
n is the additive group of
integers mod n:
Z/nZ. The cayley table for
Z/6Z is
| + | 0 | 1 | 2 | 3 | 4 | 5 |
|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 0 |
|---|
| 2 | 2 | 3 | 4 | 5 | 0 | 1 |
|---|
| 3 | 3 | 4 | 5 | 0 | 1 | 2 |
|---|
| 4 | 4 | 5 | 0 | 1 | 2 | 3 |
|---|
| 5 | 5 | 0 | 1 | 2 | 3 | 4 |
|---|
Note how each row (or column) is simply the previous row (or column) cycled forward one space.
The set of
integers mod n is not a group under multiplication because
0 has no inverse – there is nothing that multiplies
0 to give
1, the identity element for multiplication. If
n is a prime number and we throw out zero the remaining elements of
Z/nZ does form a group – a cyclic group. Here's the Cayley table for the non-zero elements of
Z (mod 7)
| × | 1 | 2 | 3 | 4 | 5 | 6 |
|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
|---|
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
|---|
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
|---|
| 5 | 5 | 3 | 1 | 6 | 4 | 2 | |
|---|
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|
The cyclic nature of the group isn't apparent from a glance at the table. However if we consider the powers of
5 then we find that
5 generates the entire group. Similarly
3 also generates the group. By rearranging the elements of the Cayley table the cyclic nature is readily seen.
| × | 1 | 5 | 4 | 6 | 2 | 3 |
|---|
| 1 | 1 | 5 | 4 | 6 | 2 | 3 |
|---|
| 5 | 5 | 4 | 6 | 2 | 3 | 1 |
|---|
| 4 | 4 | 6 | 2 | 3 | 1 | 5 |
|---|
| 6 | 6 | 2 | 3 | 1 | 5 | 4 |
|---|
| 2 | 2 | 3 | 1 | 5 | 4 | 6 | |
|---|
| 3 | 3 | 1 | 5 | 4 | 6 | 2 |
|---|
[
Exercise: The above table was rearranged by listing the
0th power of
5 first, then the first power of 5 then the 2nd power of
5 etc. Rearrange the table in order of powers of
3 such that its cyclic structure is evident.]
We can form a cyclic subgroup of any group by grabbing an element
a of the group an looking at the set of all its powers. This gives the
subgroup generated by a notated as <
a >. Now by Lagrange's theorem the number of elements in <
a > (the
order of the subgroup) must be a divisor of the order of the group. Also if
k is the order of <
a > then
k is the least positive integer with
ak = e. For any element of a group the least positive integer that gives the identity when the element is raised to that power is called the
order of the element. Thus the order of a cyclic subgroup and the order of its generator are the same number.
We might remark at this point that any subgroup of a cyclic group must itself be cyclic. If
G is generated by
a and
S is a subgroup of
G Then
S must be cyclic. To see this consider all the elements of
S. They can all be expressed as powers of
a. Let k be the least positive power of
a that is in
S. If every element is not a power of
ak then there is some element
am where m is positive and not a mulitple of k. Let p be the greatest multiple of k that is less than m. Then m - p is less than k. But this means that
am •
a-p = am-p is in
S. This contradicts the choice of k as the smallest positive power of
a in the subgroup. Thus all elements of
S are generated by
ak and
S is cyclic.
Now if for any element its order divides the order of the group then it follows that if
n is the order of the group then
an = e for any element
a of any finite group. [Why
must this be so?]
Now we have a constrained converse of Lagrange's theorem. It is true that for cyclic groups if
n is a divisor of the order of the group then the group has a subgroup of order
n. To see why this must be so recall that a cyclic group is generated by the powers of one of its elements. Let's see why this must be for
the cyclic group of order 12.
C12 = { e, a, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11}
Since 3 divides 12 (i.e. 3 × 4 = 12) then (
a3)4 = a12 = e. Thus
a3 is an element with order 4. (If it were less then a power of
a less than 12 would equal
e). Thus
a3 generates a subgroup of order 4. Similarly
a4 generates a subgroup of order 3 and
a2 generates a subgroup of order 6 while
a6 generates a subgroup of order 2. There are always the trivial subgroups of orders 1 and 12 (The subgroup containing only the identity and the whole group considered as a subgroup of itself).
There is nothing special about the number 12. Let a cyclic group have order n. If r is a divisor of n then there is some number s such that rs = n. Let
a be an element of the group with order n. (it must have one if it is cyclic) Then
ar is of order s and therefore generates a cyclic subgroup of order s while
asgenerates a subgroup of order r.
We can go a bit further in looking at subgroups of cyclic groups. Not only does a cyclic group have a subgroup of order r for every r that divides the order of the group but it has
exactly one subgroup for each distinct divisor of n. To see this suppose that
S is a subgroup of a cyclic group of order n and
a is a generator. Suppose
S has order r where rs = n. Then
S is generated by one of its elements,
ak for some k. This means that
ak has order r which in turn means that k times r equals some multiple of n. Now since rs = n, s must divide k. Therefore
ak is in the group generated by
as which is of order r. However
ak generates a group of order r. Thus r elements of the subgroup generated by
ak are in the subgroup generated by
as which has only r elements. The subgroups must be identical.
Finally let's use group theory to deduce a famous result of number theory. Consider the non-zero members of
integers mod p where p is prime. If we let our binary operation be multiplication mod p then we get a group with p-1 elements (we've thrown out zero). [Is it really a group?
- It's closed. Since p is prime any two non-zero elements (means not divisible by p) multiply to give a non-zero element.
- It's associative. Multiplication is associative in regular integers and therefore in integers mod p.
- 1 is the identity
- Since p is prime the cancellation law holds. [If ax = ay then ax - ay = a(x-y) is divisible by p. Since a is not divisible by p (or else it would be 0 mod p and that's been thrown out) x - y must be a multiple of p. This means that x = y mod p.] So the same element cannot appear twice in any row or column of the Cayley table of this system which means that every element appears once. More specifically 1 appears exactly once in every row and in every column and thus every element has an inverse.]]
If
a is in this group then
ap-1 = 1. [Why?] That means that if n is an integer that is not divisible by the prime p then
np-1 = 1 mod p
This result is known as
Fermat's Little Theorem.
Extended Euclidean Algorithm
每组数字都拆分成 rem = fst*1 - snd*quo 的形式，然后将后续的rem用前面的右面的式子替换掉，最终就能得到结果了。
Chinese Remainder Theorem
假如所求数字为x，余数分别为(a1,a2,..,ar)，模数分别为(m1,m2,...,mr)
首先求出M=m1*m2*...*mr
然后Mi = M/mi
令yi = Mi' mod mi
x则等于∑ai*Mi*yi
An element a having order p-1 mod p is called a primitive element modulo p. Observe that a is a primitive element modulo p if and only if
{a^i | 0≤i≤p-2}∈Zp*
so any elements b∈Zp* can be written as a^i where 0≤i≤p-2 in a unique way, which means gcd(i, p-1) = 1. For example, P=13, then p-1=12, if we choose a=2, then the primitive element should be 2^1 = 2; 2^5 mod 13=7, 2^7 mod 13 = 11; 2^11 mod 13 = 7.
In 2002, it was proven by Agrawal, Kayal and Saxena that there is a polynomial-time deterministic algorithm for primality testing. However, in practice, primality testing is till done mainly by using a randomized polynomial-time Monte Carlo algorithm such as the SOLOVAY-STRASSEN ALGORITHM or the MILLER-RABIN ALGORITHM.
A Las Vegas algorithm may not give an answer
Euler's generalization of fermat.
φ(N) = |(Zn)*|, for all x∈Zn*, x^φ(N) = 1 in Zn
for example, N=12, then φ(12) = {1,5,7,11}=4, 5^12=1 in Z12
