Документ взят из кэша поисковой машины. Адрес оригинального документа : http://halgebra.math.msu.su/staff/klyachko/papers/cyclic.pdf Дата изменения: Wed Feb 13 11:26:08 2013 Дата индексирования: Sat Apr 9 23:55:27 2016 Кодировка:

N ? . , . .

1

: n , n (n). : . ` ' .

arXiv:1108.5406v1 [math.GR] 27 Aug 2011

G (.. ) , (.. f , g G, f g G f -1 G). : . . [A, . 49, 5]. G g , G (.. G = {g , g 2, . . . , g n , . . . }), G . . (). n , n (n). (n) 1 n, n ( ). , n (n) , n n = p1 . . . pt (*) pi (**) pi pj - 1 i j . . . , ( ) , (., , [B]). . , [BKKSS]. (*), , p1 = p2 = p, n ( 1 , 2 , . . . , p) i ( p + 1 , p + 2 , . . . , 2 p) j ( 2 p + 1 , 2 p + 2 , . . . , 2 p +
nk ) p2

| i, j = 1, . . . , p, k = 1, . . . ,

n p2

.

(**), , p1 p2 - 1, a Zp2 , a, a2 , . . . , ap1 = 1 . Gp1 ,p2 fk,l : Z22 Z22 , p p fk,l (x, y ) := (ak x, lx + y ) k Zp1 l Zp2 . 2 ( ) n nj n . QE D ) | f Gp 1 , p 2 , j = 1 , 2 , . . . , p1 p2 p1 p2 . |X | X . G. n = |G|. , . ord a a e n, an = e. , , n . f (1 , 2 , . . . ,
1 2

. . ak l , Gp1 ,p2 = Z2в2 k Zp1 , l Zp2 p2 01
1

.


2

( ). . . G. x G {x, xf , xf 2 , . . . , xf ord f -1 }. . , ord f . xf k = y f l , y = xf k-l . x , . , |G| ord f . QED n = |G| . . , . . . x . , . G, {h1 , . . . , hm }. G {xh1 , xh2 , . . . , xhm }. |H | xhk = y hl , y = xhk h-1 . x l . , |G| m. QED

, . . f G f G ( .. ). f () f . , .. G . f ( , f ). f g G G, g = b-1 f b b G. : f . h G - f . hord h f . q n, hn f . q k Z, h-1 f h = f k . hq f , f = h-q f hq = f k ( q ). k q 1 mo d ord f . (*) ord f p1 . . . ps . k q 1 mo d pi i = 1, 2, . . . , s. |G| ord h ord h q , (*) q . (**) pj pi - 1. , q pi - 1. x = xi y = yi , q x + (pi - 1)y = 1. , k k qx+(pi -1)y 1 mo d pi i = 1, 2, . . . , s. k 1 mo d ord f , .. f h = hf . G {f i hj | 1 i ord f , 1 j q } q ord f . , (*) ord f q . (f h)j = f j hj j , ord(f h) q ord f . ord(f h) = q ord f . f , f h = G. , G . . : . X Y G xy , x X y Y . , , Y = {y }, X y X {y }.


3

(1) F Z = Z (G) := {a G : g a = ag g G}, .. , . (1). F Z . F F Z = G. . QED (2) . (2). . , , . . . , . (1) . QED (3) F , F ( F ), |G|/|F |. (3). N (F ) := {a G : F a = aF }. , N (F ) . N (F ) = G. N (F ) F , N (F ) = F . G F . u, v G F , .. u-1 F u = v -1 F v , F uv -1 = uv -1 F . , uv -1 N (F ) = F , , u F v . , u F v u-1 F u = v -1 F v . , |F v | = |F |. G, F , |F |. , , e F , |F | , |G|. QED (4) F , F . |G|/2 F < |G| - |Z |. (4). , , . (, g -1 F g F G, F g F g -1 G.) | G| |Z | (3) F = (|F | - |Z |) . = | G| 1 - |F | |F | |G| > |F |, F < |G| - |Z |. Z = F . (1) |Z | |F |. F | G| / 2 . : . F1 , . . . , Fs . , . , Fi . (2) |G| = |Z | + i Fi . (4) . (4) . QED [A] .. , , , , 1984. [B] Ken Brown, Mathematics 4340, When are all groups of order n cyclic? Cornell University, March 2009, http://www.cornell.edu/kbrown/4340/cyclic_only_orders.pdf [BKKSS] . , . , K. , . . , n ? http://olympiads.mccme.ru/lktg/2011/6/index.htm


WHEN ANY GROUP OF N ELEMENTS IS CYCLIC? V. Bragin, Ant. Klyachko and A. Skopenkov

1

We give a simple proof of the well-known fact: any group of n elements is cyclic if and only if n and (n) are coprime. This note is accessible for students b ecause no knowledge of group theory is required. The note could also b e an interesting easy reading for mature mathematicians.

arXiv:1108.5406v1 [math.GR] 27 Aug 2011

Intro duction We call a group a nonempty family G of transformations (i.e. permutations or rearrangements) of some set, which family is closed with respect to composition and taking inverse transformation (i.e. if f , g G, then f g G and f -1 G). Common term: transformation group. Cf. [A, comment to problem 5]. If a finite group G contains an element g such that G consists of all powers of g (i.e. G = {g , g 2, . . . , g n , . . . }, then group G is called cyclic . We give a simple pro of of the following well-known fact. Theorem. Any group consisting of n elements is cyclic if and only if n and (n) are coprime. Here (n) is the number of positive integers not exceeding n and coprime to n (the Euler function). Note that n and (n) are coprime if and only if in the prime decomposition n = p1 . . . pk (*) all pi are different and (**) pi do es not divide pj - 1 for any i and j . The understanding of the pro of requires no knowledge of group theory. A few necessary notions are intro duced in the course of the pro of. In particular, our arguments do es not use the notion of a quotient group, as opposed to more traditional pro ofs (see, e.g., [B]). Our pro of is possibly known. One can understand how to invent it from [BKKSS]. Pro of of the "only if" part. If condition (*) above is violated, e.g., p1 = p2 = p, then the following group consists of n elements and is not cyclic: ( 1 , 2 , . . . , p) i ( p + 1 , p + 2 , . . . , 2 p) j ( 2 p + 1 , 2 p + 2 , . . . , 2 p +
nk ) p2

| i, j = 1, . . . , p, k = 1, . . . ,

n p2

.

If condition (**) above is violated, e.g., p1 divides p2 - 1, then by the primitive ro ot theorem there is a Zp2 for which the powers a, a2 , . . . , ap1 = 1 are different. Denote by Gp1 ,p2 the group of transformations fk,l : Z22 Z22 defined by the formula fk,l (x, y ) := (ak x, lx + y ) for k Zp1 p p and l Zp2 . 2 Then the following group is not cyclic (it is even nonabelian): f (1 , 2 , . . . , nj ) |f G p1 p2
p 1 ,p
2

, j = 1, 2, . . . ,

n p1 p

. QE D
2

Pro of of the "if" part. We use the induction on the number of prime factors of |G|. If this order is prime, then the "if" part is implied by the following Lagrange Theorem. The order ord a of an element a of a group with the identity element e is the minimal positive integer n such that an = e. If the group is finite, it is clear that such n exists. Lagrange Theorem (particular case). The number of elements of any finite group is divisible by the order of any its element.
1We 2I

would like to acknowledge K. Kohas for useful discussions. ak l n more advanced notation Gp1 ,p2 := Z2в2 k Zp1 , l Zp2 p2 01
1

.


2

Proof. Denote the group by G. For each x G consider the set {x, xf , xf 2 , . . . , xf ord f -1 }. By the definition of order these elements are different. Therefore this set contains ord f elements. If xf k = y f l , then y = xf k-l . Therefore for different x these sets either coincide or are disjoint. Thus |G| is divisible by ord f . QED Now suppose that the number of factors is greater than one. We need the following general version of the Lagrange Theorem. A subgroup of a group G is a subset of G that is itself a group. Lagrange Theorem. The number of elements of any finite group is divisible by the number of elements of any subgroup. Proof. Denote the group by G and the subgroup by {h1 , h2 , . . . , hm }. For each x G consider the set {xh1 , xh2 , . . . , xhm }. This set contains m elements. If xhk = y hl , then y = xhk h-1 . Therefore l for different x these sets either coincide or are disjoint. Thus |G| is divisible by m. QED A maximal subgroup of a group is a maximal by inclusion subgroup not coinciding with G and containing more than one element. By the induction hypothesis and the Lagrange Theorem, each maximal subgroup is cyclic. For an element f of a group G let f be the set of all powers of f (including zero and negative ones). The element f is called generating for the (cyclic) subgroup f . Suppose to the contrary that the group G is noncyclic. Then each element is contained in a maximal subgroup. Elements f , g of a group G are conjugate in G if g = b-1 f b for some b G. First case: generator f of some maximal subgroup is conjugate only to (some of ) its powers. Take h G \ f . Then hord h f . Let q be the minimal positive integer such that hn f . q Take k Z such that h-1 f h = f k . The inclusion hq f implies f = h-q f hq = f k (here the last equality is proved by induction on q ). Therefore k q 1 mo d ord f . By condition (*) and the Lagrange Theorem ord f is a pro duct p1 . . . ps of different primes. Then k q 1 mo d pi for any i = 1, 2, . . . , s. Since |G| is divisible by ord h and ord h is divisible by q , by condition (*) we obtain that q is a pro duct of different primes. By condition (**) none of these primes pj divides none pi - 1. Therefore q is coprime to each pi - 1. Hence there exist integers x = xi and y = yi such that q x + (pi - 1)y = 1. Therefore k k qx+(pi-1)y 1 mo d pi for any i = 1, 2, . . . , s. Hence k 1 mo d ord f , i.e., f h = hf . Then G contains a subgroup {f i hj | 1 i ord f , 1 j q } of q ord f elements. Hence by condition (*) and the Lagrange Theorem ord f is coprime to q . Since (f h)j = f j hj for each j , we obtain that ord(f h) is divisible both by q and by ord f . ord(f h) = q ord f . Thus ord(f h) = q ord f . Since the subgroup f is maximal, we have f h = G and G is cyclic. Contradiction. Second case: generator of any maximal subgroup is conjugate not only to its powers. The pro duct of subsets X and Y of a group G is the set of all pro ducts xy , where x X and y Y . If one of these subsets consists of only one element, e.g., Y = {y }, then we write X y instead of X {y }. (1) Any maximal subgroup F contains the center Z = Z (G) := {a G : g a = ag for any g G}, i.e., the set of elements commuting with each element of the group. Proof of assertion (1). Otherwise F Z is a larger commutative subgroup. By the maximality of F we have F Z = G, which contradicts to the assumption of the second case. QED (2) The intersection of two maximal subgroups equals the center. Proof of assertion (2). A nontrivial element of the intersection commutes with all elements of both subgroups. Hence it commutes with any pro duct of several multiples, each multiple being an element of one of our subgroups. The set of such pro ducts is a subgroup. By the maximality of our


3

subgroups this subgroup coincides with the entire group. Therefore the intersection is contained in the center. Assertion (1) implies the converse inclusion. QED (3) The number of different subgroups conjugate to a maximal subgroup F (including F ) is | G| / | F | . Proof of assertion (3). Consider the set N (F ) := {a G : F a = aF }. It is easy to verify that N (F ) is a subgroup. By the assumption of the second case N (F ) = G. Since N (F ) F , the maximality implies that N (F ) = F . The conjugation by each element of G takes F to a conjugate subgroup. If the conjugation by two different elements u and v takes the F to the same subgroup, i.e., u-1F u = v -1 F v , then F uv -1 = uv -1F . This means that uv -1 N (F ) = F or, equivalently, u F v . Conversely, the condition u F v implies u-1F u = v -1 F v . Clearly, |F v | = |F |. Therefore the number of elements of G conjugation by which takes F to a given subgroup equals |F |. Therefore the number of different subgroups conjugate to F is precisely |F | times less than |G|. QED umber of elements of G conjugate to elements of a maximal subgroup F center. Then |G|/2 F < |G| - |Z |. A subgroup conjugate to a maximal subgroup is also maximal. (Indeed, F g F g -1 G.) | G| |Z | Therefore by (3) F = (|F | - |Z |) . = | G| 1 - |F | |F | The inequality |G| > |F | implies F < |G| - |Z |. By the assumption of the second case, Z = F . By (1) and the Lagrange theorem, |Z | divides |F |. Therefore F |G|/2. Conclusion of the proof of the second case: calculations. Let F1 , . . . , Fn be a maximal family of pairwise non-conjugate maximal subgroups. Recall that each element of the group is contained in some maximal subgroup. Hence the element is conjugate to some element in certain Fi . By this and (2) |G| = |Z | + i Fi . By the left inequality in (4), the number of summands is at most one. By the right inequality in (4), one summand also gives a contradiction. QED References [A] V. I. Arnold, Ordinary Differential Equations, The MIT Press (1978), ISBN 0-262-51018-9. [B] Ken Brown, Mathematics 4340, When are all groups of order n cyclic? Cornell University, March 2009, http://www.cornell.edu/kbrown/4340/cyclic only orders.pdf [BKKSS] D. Baranov, A. Klyachko, K. Kohas, A. Skopenkov and M. Skopenkov, When are all groups of order n cyclic? http://olympiads.mccme.ru/lktg/2011/6/index.htm (4) Denote by F the n and not contained in the Proof of assertion (4). if g -1 F g F G, then