\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}}
\let\phi\varphi
\frenchspacing
\textwidth=17.4cm\textheight=25.5cm\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{{\bf WHEN ANY GROUP OF $N$ ELEMENTS IS CYCLIC?}
\footnote{See update version on www.arxiv.org.
We would like to acknowledge K. Kohas for useful discussions.}
}
\smallskip
\centerline{\bf V. Bragin, Ant. Klyachko, and A. Skopenkov}

\bigskip

\small
We give a simple proof of the well-known fact: any group of $n$-elements is cyclic if and only if
$n$ and $\phi(n)$ are coprime.
This paper is accessible for high-school students because no knowledge of group theory is required.
It could also be an interesting easy reading for mature mathematicians.

\normalsize

\bigskip
{\bf Introduction}

We call a {\it 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\in G$, then $f\circ g\in G$ and $f^{-1}\in 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,\dots,g^n,\dots\}$, then group $G$ is called {\it cyclic\/}.

We prove the following theorem.

\smallskip
{\bf Theorem (folklore).}
{\it Any group consisting of $n$ elements is cyclic if and only if $n$ and $\phi(n)$ are coprime.}

\smallskip
Here $\phi(n)$ is the number of positive integers not exceeding
$n$ and coprime to $n$ (the Euler function).

Note that $n$ and $\phi(n)$ are coprime if and only if
in the prime decomposition $n=p_1\dots p_k$

(*) all $p_i$ are different and

(**) $p_i$ does not divide $p_j-1$ for any $i$ and $j$.

The understanding of the proof requires no knowledge of group theory.
A few necessary notions are introduced in the course of the proof.
In particular, our arguments does not use the notion of a quotient group,
as opposed to more traditional proofs (see, e.g., [B]).
Our proof uses ideas similar to [???].
One can understand how to invent this proof from [BKKSS].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
{\bf Proof of the ``only if" part.}

If condition (*) above is violated, e.g., $p_1=p_2=p$, then the following group
consists of $n$ elements and is not cyclic:
$$\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\}.$$
\quad
If condition (**) above is violated, e.g., $p_1$ divides $p_2-1$, then by the primitive root theorem
there is $a\in\Z_{p_2}^*$ for which the powers $a,a^2,\dots,a^{p_1}=1$ are different.
Denote by $G_{p_1,p_2}$ the group of transformations
$f_{k,l}:\Z_{p_2}^2\to \Z_{p_2}^2$ defined by the formula
$f_{k,l}(x,y):=(a^kx,lx+y)$ for $k\in\Z_{p_1}$ and $l\in\Z_{p_2}$.
\footnote{In more advanced notation
$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\}.
$}
Then the following group is not cyclic (it is even nonabelian):
$$\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$$
 
%As opposed to $\Z/k$, the object $\Z_k$ is the {\it set} having summation and multiplication operations known from number theory.
%\newline
%Denote $\Z/k:=\{(12\dots k)^j\ |\ j=1,2,\dots,k\}$.
%If $g$ and $h$ are transformations of sets $M$ and $N$, respectively, then transformations
%$g\times h$ of the Cartesian product $M\times N$ is defined by $(g\times h)(x,y):=(g(x),h(y))$.
%Denote $G\oplus H=\{g\times h\ |\ g\in G,\ h\in H\}$.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
{\bf Proof 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 {\bf order} $\ord a$ of an element $a$ of a group with the identity
element $e$ is the minimal positive integer $n$ such that $a^n=e$.
If the group is finite, it is clear that such $n$ exists.

\smallskip
{\bf Lagrange Theorem (particular case).}
{\it The number of elements of any finite group is divisible by the order of any its element.}

\smallskip
{\it Proof.} Denote the group by $G$.
For each $x\in G$ consider the set
$\{x,xf,xf^2,\dots,xf^{\ord f-1}\}$.
 By the definition of order these elements are different.
Therefore this set contains $\ord f$ elements.
If $xf^k=yf^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

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

\smallskip
Now suppose that the number of factors is greater than one.
We need the following general version of the Lagrange Theorem.

A {\bf subgroup} of a group $G$ is a subset of $G$ that is itself a group.

\smallskip
{\bf Lagrange Theorem.}
{\it The number of elements of any finite group is divisible by the number of elements of any subgroup.}

\smallskip
{\it Proof.} Denote the group by $G$ and the subgroup by $\{h_1,h_2,\dots,h_m\}$.
For each $x\in G$ consider the set $\{xh_1,xh_2,\dots,xh_m\}$.
 This set contains $m$ elements.
If $xh_k=yh_l$, then $y=xh_kh_l^{-1}$.
Therefore for different $x$ these sets either coincide or are disjoint.
Thus $|G|$ is divisible by $m$.
QED

\smallskip

A {\bf 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, {\it each maximal subgroup is cyclic.}

For an element $f$ of  a group $G$ let $\gp f$ be the set of all powers of $f$ (including zero and negative ones).
The element $f$ is called {\bf generating} for the (cyclic) subgroup  $\gp 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 {\bf conjugate} in $G$ if $g=b^{-1}fb$ for some $b\in G$.

\smallskip
{\bf First case:} {\it generator $f$ of some maximal subgroup is conjugate only to (some of) its powers.}
Take $h\in G\setminus\gp f$.
Then $h^{\ord h}\in \gp f$.
Let $q$ be the minimal positive integer such that $h^n\in \gp f$.
Take $k\in\Z$ such that $h^{-1}fh=f^k$.
The inclusion $h^q\in\gp f$ implies $f=h^{-q}fh^q=f^{k^q}$ (here the last equality is proved by induction on $q$).
Therefore $k^q\equiv1\mod\ord f$.

By condition (*) and the Lagrange Theorem $\ord f$ is a product $p_1\dots p_s$ of different primes.
Then $k^q\equiv1\mod p_i$ for any $i=1,2,\dots,s$.
Since $|G|$ is divisible by $\ord h$ and $\ord h$ is divisible by $q$,
by condition (*) we obtain that $q$ is a product of different primes.
By condition (**) none of these primes $p_j$ divides none $p_i-1$.
Therefore $q$ is coprime to each $p_i-1$.
Hence there exist integers $x=x_i$ and $y=y_i$ such that $qx+(p_i-1)y=1$.
Therefore $k\equiv k^{qx+(p_i-1)y}\equiv1\mod p_i$ for any $i=1,2,\dots,s$.
Hence $k\equiv1\mod\ord f$, i.e., $fh=hf$.

Then $G$ contains a subgroup $\{f^ih^j\ |\ 1\le i\le \ord f,\ 1\le j\le q\}$ of $q\ord f$ elements.
Hence by condition (*) and the Lagrange Theorem $\ord f$ is coprime to $q$.
Since $(fh)^j=f^jh^j$ for each $j$, we obtain that $\ord(fh)$ is divisible both by $q$ and by $\ord f$.
������� $\ord(fh)=q\ord f$.
Thus $\ord(fh)=q\ord f$.
Since the subgroup $\gp f$ is maximal, we have $\gp{fh}=G$ and $G$ is cyclic.
Contradiction.


\smallskip
{\bf Second case:} {\it generator of any maximal subgroup is conjugate not only to its powers.}

The {\bf product of subsets $X$ and $Y$} of a group $G$ is the
set of all products $xy$, where $x\in X$ and $y\in Y$.
If one of these subsets consists of only one element,
e.g., $Y=\{y\}$, then we write $Xy$ instead of $X\{y\}$.

\smallskip
{\it (1) Any maximal subgroup $F$ contains the} {\bf center}
$$
Z=Z(G):=\{a\in G\ :\ ga=ag\text{ for any }g\in G\},
$$
{\it i.e., the set of elements commuting with each element of the group.}

\smallskip
{\it Proof of assertion (1).}
Otherwise $FZ$ is a larger commutative subgroup.
By the maximality of $F$ we have $FZ=G$, which
contradicts to the assumption of the second case. QED

\smallskip
{\it (2) The intersection of two maximal subgroups equals the center.}

\smallskip
{\it Proof of assertion (2).}
A nontrivial element of the intersection commutes with all elements of both subgroups.
Hence it commutes with any product of several multiples, each multiple being an element of one of our subgroups.
The set of such products is a subgroup.
By the maximality of our subgroups this subgroup coincides with the entire group.
Therefore the intersection is contained in the center.

Assertion (1) implies the converse inclusion.  QED

\smallskip
{\it (3) The number of different subgroups conjugate to a maximal subgroup $F$
(including $F$) is $|G|/|F|$.}

\smallskip
{\it Proof of assertion (3).}
Consider the set
$$
N(F):=\{a\in G\ :\ Fa=aF\}.
$$
It is easy to verify that $N(F)$ is a subgroup.
By the assumption of the second case $N(F)\ne G$.
Since $N(F)\supset 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^{-1}Fu=v^{-1}Fv$, then $Fuv^{-1}=uv^{-1}F$.
This means that $uv^{-1}\in N(F)=F$ or, equivalently, $u\in Fv$.
Conversely, the condition $u\in Fv$ implies $u^{-1}Fu=v^{-1}Fv$.

Clearly, $|Fv|=|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


\smallskip
{\it (4) Denote by $\widehat F$ the number  of elements of $G$ conjugate to elements of a
maximal subgroup $F$ and not contained in the center.
Then $|G|/2\le \widehat F<|G|-|Z|$.}

\smallskip
{\it Proof of assertion (4).}
A subgroup conjugate to a maximal subgroup is also maximal.
(Indeed, if $g^{-1}Fg\subset F'\subset G$, then $F\subset gF'g^{-1}\subset G$.)

Therefore by (3)
$\widehat F=(|F|-|Z|)\dfrac{|G|}{|F|}=|G|\left(1-\dfrac{|Z|}{|F|}\right)$.

The inequality $|G|>|F|$ implies $\widehat F<|G|-|Z|$.

By the assumption of the second case, $Z\ne F$.
%By the induction hypothesis, $Z=\gp z$ for some $z\in Z$.
By (1) and the Lagrange theorem, $|Z|$
%=\ord z$
divides $|F|$.
Therefore $\widehat F\ge|G|/2$.

\smallskip
{\it Conclusion of the proof of the second case: calculations.}
Let $F_1,\dots,F_n$ 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 $F_i$.
By this and (2) $|G|=|Z|+\sum_i \widehat{F_i}$.
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



\bigskip
\centerline{\bf References}

[A] 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] D. Baranov, A. Klyachko, K. Kohas, A. Skopenkov and M. Skopenkov,
When are all groups of order $n$ are cyclic? Materials of LKTG 2011, http://olympiads.mccme.ru/lktg/



\end{document}

 