\documentclass[reqno,12pt,draft]{amsart}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epic,eepic}
%\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\def\R{{\bf R}} \def\Z{{\bf Z}} \def\C{{\bf C}} \def\Q{{\bf Q}} \def\Z{\mathbb{Z}}
\def\ord{\mathop{\fam0 ord}}
\def\ind{\mathop{\fam0 ind}}
\def\id{\mathop{\fam0 id}}
\textwidth=17.4cm\textheight=25.6cm\hoffset=-2.5cm\voffset=-3cm
%\textwidth=18.2cm\textheight=27cm\hoffset=-2.9cm\voffset=-3.2cm
%\pagestyle{empty}
%\nopagenumbers
\long\def\comment#1\endcomment{}
\theoremstyle{definition}
\newtheorem{pr}{}[section]

\begin{document}

\centerline{\uppercase{\bf Когда любая группа из $N$ элементов циклическая?}
\footnote{Обновляемая версия поддерживается на www.arxiv.org.
Благодарим К. Кохася за полезные замечания.}
}
\smallskip
\centerline{\bf В. Брагин, Ант. Клячко и А. Скопенков}

\bigskip

\small
В этой заметке приводится простое
доказательство известного факта: любая группа из $n$ элементов является
циклической тогда и только тогда, когда $n$ взаимно просто с $\phi(n)$.
Заметка доступна школьникам: для понимания не требуется знаний по теории групп.
Она может быть также интересным `легким чтением' для профессиональных математиков.

\normalsize

\bigskip
{\bf Введение}

Назовем {\it группой} непустое семейство $G$ преобразований (т.е.  перестановок) некоторого множества, замкнутое относительно композиции и взятия обратного преобразования (т.е. если $f,g\in G$, то $f\circ g\in G$ и $f^{-1}\in G$). Общепринятое название: группа преобразований.
Ср. [A, стр. 49, комментарий к задаче 5].

Если в конечной группе $G$ найдется преобразование $g$, из всех возможных степеней которого состоит $G$
(т.е. $G=\{g,g^2,\dots,g^n,\dots\}$), то группа $G$ называется {\it циклической\/}.

Мы докажем следующую теорему.

\smallskip
{\bf Теорема (фольклор).} {\it Любая группа из $n$ элементов является
циклической тогда и только тогда, когда $n$ взаимно просто с $\phi(n)$.}

\smallskip
Здесь $\phi(n)$  --- количество целых чисел от 1 до $n$, взаимно простых с $n$ (функция Эйлера).

Заметим, что условие взаимной простоты $n$ и $\phi(n)$ равносильно тому,
что в разложении числа~$n$ на простые сомножители $n=p_1\dots p_t$

(*) все $p_i$ различны и

(**) $p_i$ не делит $p_j-1$ ни для каких $i$ и $j$.

Для понимания доказательства не требуется никаких знаний по теории групп.
Небольшое количество необходимых понятий вводятся в процессе доказательства.
В частности, наше доказательство не привлекает (явно или неявно) понятия факторгруппы,
в отличие от более традиционных доказательств (см., например, [B]).
Идея приводимого доказательства близка к [???].
Как придумать приводимое доказательство, видно из [BKKSS].



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
{\bf Доказательство части <<только тогда>>}

Если нарушается вышеприведенное условие (*), например, $p_1=p_2=p$, то в качестве
нециклической группы из $n$ элементов можно взять группу
$$\left\{(1,2,\dots,p)^i(p+1,p+2,\dots,2p)^j(2p+1,2p+2,\dots,2p+\tfrac n{p^2})^k\ |\ i,j=1,\dots,p,\ k=1,\dots,\tfrac n{p^2}\right\}.$$
%$\Z/p_1\oplus\Z/p_2\oplus\Z/\frac n{p_1p_2}$.
\quad
Если нарушается вышеприведенное условие (**), например, $p_1$ делит $p_2-1$,
то по теореме о первообразном корне существует элемент $a\in\Z_{p_2}$, для которого степени $a,a^2,\dots,a^{p_1}=1$ различны.
Обозначим через $G_{p_1,p_2}$ группу преобразований $f_{k,l}:\Z_{p_2}^2\to \Z_{p_2}^2$, заданных  формулой $f_{k,l}(x,y):=(a^kx,lx+y)$ для $k\in\Z_{p_1}$ и $l\in\Z_{p_2}$.
\footnote{
%В отличие от $\Z/k$, объект $\Z_k$ рассматривается как {\it множество} с операциями суммы и произведения, известными из теории чисел.
%\newline
Научно говоря,
$G_{p_1,p_2}=\left\{
\begin{pmatrix}
a^k&l\cr
0&1\cr
\end{pmatrix}\in\Z_{p_2}^{2\times2}
\;\Big|\;
k\in\Z_{p_1},\ l\in\Z_{p_2}\;
\right\}.$}
%Обозначим $\Z/k:=\{(12\dots k)^j\ |\ j=1,2,\dots,k\}$.
%Если $g$ и $h$ --- преобразования множеств $M$ и $N$, соответственно, то  преобразование
%$g\times h$ декартова произведения $M\times N$ определяется формулой $(g\times h)(x,y):=(g(x),h(y))$.
%Обозначим $G\oplus H=\{g\times h\ |\ g\in G,\ h\in H\}$.
Тогда в качестве нециклической (даже некоммутативной) группы из $n$ элементов можно взять группу
$$\left\{f\circ(1,2,\dots,\frac n{p_1p_2})^j\ |\ f\in G_{p_1,p_2},\ j=1,2,\dots,\frac n{p_1p_2}\right\}.\quad QED$$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bigskip
{\bf Доказательство части <<тогда>>.}

Через $|X|$ обозначается число элементов в множестве $X$.
Обозначим данную группу через $G$.
Используем индукцию по числу простых сомножителей в $n=|G|$.
Если сомножитель один, то часть <<тогда>> вытекает из следующей теоремы Лагранжа.

{\bf Порядком} $\ord a$ элемента $a$ группы с единичным элементом $e$ называется наименьшее
целое положительное $n$, для которого $a^n=e$.
Если группа конечна, то ясно, что такое $n$ существует.

\smallskip
{\bf Теорема Лагранжа (частный случай).} {\it Число элементов конечной группы делится на порядок любого ее элемента.}

\smallskip
{\it Доказательство.} Обозначим данную группу через $G$.
Для любого $x\in G$ рассмотрим множество
%\linebreak
$\{x,xf,xf^2,\dots,xf^{\ord f-1}\}$.
По определению порядка указанные элементы различны.
Значит, в этом множестве $\ord f$ элементов.
Если $xf^k=yf^l$, то $y=xf^{k-l}$.
Поэтому для разных $x$ эти множества либо не пересекаются, либо совпадают.
Значит, $|G|$ делится на $\ord f$.
QED

\def\gp#1{\left\langle#1\right\rangle}


\smallskip
Пусть теперь простых сомножителей в $n=|G|$ больше одного.
Нам понадобится следующая общая версия теоремы Лагранжа.

{\bf Подгруппой} группы называется подмножество этой группы, которое само по себе является группой.

\smallskip
{\bf Теорема Лагранжа.} {\it Число элементов конечной группы делится на число элементов любой ее подгруппы.}

\smallskip
{\it Доказательство.} Обозначим данную группу через $G$, а ее подгруппу через $\{h_1,\dots,h_m\}$.
Для любого $x\in G$ рассмотрим множество
%\linebreak
$\{xh_1,xh_2,\dots,xh_m\}$.
В этом множестве $|H|$ элементов.
Если $xh_k=yh_l$, то $y=xh_kh_l^{-1}$.
Поэтому для разных $x$ эти множества либо не пересекаются, либо совпадают.
Значит, $|G|$ делится на $m$.
QED

\smallskip
{\bf Максимальной подгруппой} назовем максимальную по включению подгруппу, не совпадающую со всей группой и содержащую более одного элемента.
По предположению индукции и теореме Лагранжа {\it каждая максимальная подгруппа является циклической.}

Для элемента $f$ группы $G$ обозначим через $\gp f\subset G$ множество всех его степеней (в т.ч. нулевых и отрицательных).
Элемент $f$ называется {\bf порождающим} для (циклической) подгруппы $\gp f$.

Предположим противное, т.е. что группа $G$ не является циклической.
Тогда {\it каждый элемент $f$ содержится в некоторой максимальной подгруппе} (в максимальной по включению подгруппе, содержащей $\gp f$).

Элементы $f$ и $g$ группы $G$ называются {\bf сопряженными} в $G$, если $g=b^{-1}fb$ для некоторого $b\in G$.

\smallskip
{\bf Первый случай:} {\it порождающий элемент $f$ некоторой максимальной подгруппы сопряжен только с некоторыми своими степенями.}
Возьмем $h\in G-\gp f$.
Тогда $h^{\ord h}\in \gp f$.
Обозначим через $q$ наименьшее из целых положительных $n$, для которых $h^n\in \gp f$.
Возьмем $k\in\Z$, для которого $h^{-1}fh=f^k$.
Так как $h^q\in\gp f$, то $f=h^{-q}fh^q=f^{k^q}$ (последнее равенство доказывается индукцией по $q$).
Поэтому $k^q\equiv1\mod\ord f$.

По условию (*) и теореме Лагранжа $\ord f$ является произведением $p_1\dots p_s$ различных простых.
Тогда $k^q\equiv1\mod p_i$ для любого $i=1,2,\dots,s$.
Так как $|G|$ делится на $\ord h$ и $\ord h$ делится на $q$, то по условию (*) $q$ является произведением различных простых.
По условию (**) ни одно из этих простых $p_j$ не делит никакое $p_i-1$.
Следовательно, $q$ взаимно просто с каждым $p_i-1$.
Поэтому существуют целые $x=x_i$ и $y=y_i$, для которых $qx+(p_i-1)y=1$.
Значит, $k\equiv k^{qx+(p_i-1)y}\equiv1\mod p_i$ для любого $i=1,2,\dots,s$.
Поэтому $k\equiv1\mod\ord f$, т.е. $fh=hf$.

Тогда в $G$ есть подгруппа $\{f^ih^j\ |\ 1\le i\le \ord f,\ 1\le j\le q\}$ из $q\ord f$ элементов.
Значит, по условию (*) и теореме Лагранжа $\ord f$ и $q$ взаимно просты.
Так как $(fh)^j=f^jh^j$ для любого $j$, то $\ord(fh)$ делится на $q$ и на $\ord f$.
Поэтому $\ord(fh)=q\ord f$.
Так как подгруппа $\gp f$ максимальна, то $\gp{fh}=G$.
Значит, $G$ циклическая. Противоречие.

\smallskip
{\bf Второй случай:} {\it порождающий элемент любой максимальной подгруппы сопряжен не только со своими степенями.}

{\bf Произведением двух подмножеств $X$ и $Y$} группы $G$ называют
множество всевозможных произведений $xy$, где $x\in X$ и $y\in Y$.
Если одно из этих подмножеств состоит только из одного элемента,
например, $Y=\{y\}$, то для краткости пишут $Xy$ вместо
$X\{y\}$.

\smallskip
{\it (1) Любая максимальная подгруппа $F$ содержит} {\bf центр}
$$Z=Z(G):=\{a\in G\ :\ ga=ag\text{ для любого }g\in G\},$$
{\it т.е. множество тех элементов, которые коммутируют со всеми.}

%:=\{fz\in G\ :\ f\in F,\ z\in Z\}$

\smallskip
{\it Доказательство утверждения (1).}
Иначе $FZ$ --- большая коммутативная подгруппа.
Ввиду максимальности $F$ имеем $FZ=G$.
Противоречие с условием второго случая. QED

\smallskip
{\it (2) Пересечение двух максимальных подгрупп равно центру.}

\smallskip
{\it Доказательство утверждения (2).}
Неединичный элемент в пересечении коммутирует с элементами обоих подгрупп.
Значит, он коммутирует с любым произведением нескольких сомножителей, каждый из которых
лежит в одной из наших подгрупп.
Множество таких произведений является подгруппой.
В силу максимальности наших подгрупп эта подгруппа совпадает со всей группой.
Значит, пересечение содержится в центре.

Из (1) вытекает обратное включение.
QED

\smallskip
{\it (3) Для любой максимальной подгруппы $F$
число различных подгрупп, сопряженных с $F$ (включая $F$), равно $|G|/|F|$. }

\smallskip
{\it Доказательство утверждения (3).}
Рассмотрим множество
$$N(F):=\{a\in G\ :\ Fa=aF\}.$$
%Пусть $F=\gp f$.
%Рассмотрим множество
%$$N(f):=\{a\in G\ :\ fa=af^k\text{ для некоторого }k\}.$$
Нетрудно проверить, что $N(F)$ является подгруппой.
По условию второго случая $N(F)\ne G$.
Так как $N(F)\supset F$, то в силу максимальности $N(F)=F$.

Сопряжение каждым элементом группы $G$ переводит подгруппу $F$ в одну из сопряженных подгрупп.
Если сопряжение двумя разными элементами $u,v$ группы $G$ переводит подгруппу $F$ в одну и ту же подгруппу, т.е.
$u^{-1}Fu=v^{-1}Fv$, то $Fuv^{-1}=uv^{-1}F$.
Это означает, что $uv^{-1}\in N(F)=F$ или, что то же самое, $u\in Fv$.
Обратно, условие $u\in Fv$ влечет $u^{-1}Fu=v^{-1}Fv$.

Ясно, что $|Fv|=|F|$.
Поэтому число элементов в $G$, сопряжение с которыми переводит подгруппу $F$ в данную фиксированную сопряженную подгруппу, равно $|F|$.
Значит, число подгрупп, сопряжeнных к $F$, ровно в $|F|$ раз меньше, чем $|G|$. QED


\smallskip
{\it (4) Обозначим через $\widehat F$ число элементов, сопряженных элементам максимальной подгруппы $F$ и не лежащих в центре.
Тогда $|G|/2\le \widehat F<|G|-|Z|$.}

\smallskip
{\it Доказательство утверждения (4).}
Подгруппа, сопряженная к максимальной, также максимальна.
(Действительно, если $g^{-1}Fg\subset F'\subset G$, то
$F\subset gF'g^{-1}\subset G$.)

Поэтому и ввиду (3) $\widehat F=(|F|-|Z|)\dfrac{|G|}{|F|}=|G|\left(1-\dfrac{|Z|}{|F|}\right)$.

Так как $|G|>|F|$, то $\widehat F<|G|-|Z|$.

По условию второго случая $Z\ne F$.
%По предположению индукции $Z=\gp z$ для некоторого $z\in Z$.
По (1) и теореме Лагранжа $|Z|$
%=\ord z$
делит $|F|$.
Поэтому $\widehat F\ge|G|/2$.

\smallskip
{\it Завершение разбора второго случая: подсчет.}
Пусть $F_1,\dots,F_s$ --- наибольший набор попарно несопряженных максимальных подгрупп.
Напомним, что любой элемент группы содержится в некоторой максимальной подгруппе.
Значит, он сопряжен некоторому элементу в некоторой подгруппе $F_i$.
Тогда ввиду (2) $|G|=|Z|+\sum_i \widehat{F_i}$.
Ввиду левого неравенства в (4) число слагаемых не превосходит единицы.
Ввиду правого неравенства в (4) одного слагаемого тоже быть не может.
QED




\bigskip
\centerline{\bf Литература}

[A] В.И. Арнольд, Обыкновенные дифференциальные уравнения, М, Наука, 1984.
%V.~I.~Arnold, Ordinary Differential Equations, Springer, Berlin, 19??.

[B] Ken Brown,
Mathematics 4340, When are all groups of order $n$ cyclic?
Cornell University, March 2009,
%\newline{\tt
http://www.cornell.edu/~kbrown/4340/cyclic\_only\_orders.pdf

[BKKSS] Д. Баранов, А. Клячко, K. Кохась, А. Скопенков и М. Скопенков,
Когда любая группа из $n$ элементов циклическая?
Материалы ЛКТГ 2011, http://olympiads.mccme.ru/lktg 

\end{document}

{\it (3) Для подгруппы $H$ рассмотрим множество
%$$N(f):=\{a\in G\ :\ fa=af^k\text{ для некоторого }k\}.$$
$$N(H):=\{a\in G\ :\ Ha=aH\}.$$
Число различных подгрупп, сопряженных с подгруппой $H$ (включая $H$), равно $|G|/|N(H)|$.}

\smallskip
{\it Доказательство утверждения (3).}
Действительно, сопряжение каждым элементом группы $G$ переводит подгруппу $H$ в одну из сопряженных подгрупп.
Если сопряжение двумя разными элементами $u,v$ группы $G$ переводит подгруппу $H$ в одну и ту же подгруппу, т.е.
$u^{-1}Hu=v^{-1}Hv$, то $(uv^{-1})^{-1}Huv^{-1}=H$.
Это означает, что $uv^{-1}\in N(H)$ или, что то же самое, $u\in N(H)v$.
Обратно, условие $u\in N(H)v$ влечет $u^{-1}Hu=v^{-1}Hv$.

Ясно, что $|N(H)v|=|N(H)|$.
Поэтому число элементов в $G$, сопряжение с которыми переводит подгруппу $H$ в данную фиксированную сопряженную подгруппу, равно $|N(H)|$.
Значит, число подгрупп, сопряжeнных к $H$, ровно в $|N(H)|$ раз меньше, чем элементов группы $G$. QED


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
{\bf Комментарии}

%{\bf Можно добавить комментарии из версии 3.07 от Антона}


\smallskip
{\it Немного другое доказательство части <<тогда>>}
получается, если вместо (1) доказать следующее.

\smallskip
{\it (1') Только единичный элемент коммутирует со всеми.}

\smallskip
{\it Доказательство утверждения (1').}
%Назовем {\it центром} группы $G$ множество
%$$Z:=\{a\in G\ :\ ga=ag\text{ для любого }g\in G\}$$
%тех элементов, которые коммутируют со всеми.
%Ясно, что центр --- подгруппа.
По условию второго случая $Z\ne G$.
Значит, по предположению индукции центр цикличен: $Z=\gp z$.

Назовем элементы $a,b\in G$ {\it левосравнимыми по модулю $z$}, если $a=bz^k$ для некоторого $k\in\Z$.
Обозначение: $a\equiv b\mod z$.
Обозначим через $[a]$ класс левосравнимости элемента $a$ по модулю $z$.
Обозначим через $G_z$ множество классов левосравнимости по модулю $z$.
Операция $*$ на $G_z$ корректно определена формулой $[a]*[b]:=[ab]$.

Значит, по предположению индукции существует $g\in G_z$, для которого
$G_z=\gp g$.
(Чтобы применить предположение индукции, нужно либо воспользоваться нижеследующей теоремой Кэли о том, то $G_z$ есть группа преобразований, либо доказывать основное утверждение для групп в общепринятом определении.)
Возьмем $h\in G$, для которого $g=[h]$.
Тогда $G=\gp{zh}$ циклическая --- противоречие c условием второго случая.

\smallskip
{\bf Теорема Кэли (частный случай).} {\it Пусть $G$ --- группа и для $z\in G$ операция $*$ на $G_z$ корректно определена формулой $[a]*[b]:=[ab]$.
Тогда $(G_z,*)$ изоморфна некоторой группе перестановок множества $G_z$.
Иными словами, существует взаимно-однозначное (т.е. инъективное) отображение
$\varphi:G_z\to S_{|G_z|}$, для которого $\varphi(x*y)=\varphi(x)\circ\varphi(y)$. }

%\smallskip
%{\it Доказательство.} Аналогично решению задачи \ref{pr-numbers}c.

