\documentclass[12pt]{article}
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\usepackage{amsfonts,amsmath}
\bibliographystyle{plain}

%some special symbols and my theorem environments
\def\Z{\mathbb {Z}}
\def\qed{{\hfill\vrule height 5pt width 5pt depth 0pt}}
\def\phi{\varphi}
\def\cS{\cal S}
\def\Aut{\mathop{\rm Aut}}
\def\qed{{\hfill\vrule height 5pt width 5pt depth 0pt}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newenvironment{remark}{\noindent{\bf Remark.\ }}{\hfill}

\begin{document}
\vspace*{-60pt} 
\centerline{\smalltt INTEGERS: 
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5(1) 
(2005), \#A26} 
\vskip 50pt

\begin{center}
{\bf DERIVING DIVISIBILITY THEOREMS WITH BURNSIDE'S THEOREM}
\vskip 20pt
{\bf Tyler J. Evans}\\
{\smallit Department of Mathematics, Humboldt State University, Arcata, CA
  95521,  USA}\\
{\tt evans@humboldt.edu}\\
\vskip 10pt
{\bf Benjamin V. Holt}\\
{\smallit Department of Mathematics, Humboldt State University, Arcata, CA
  95521,  USA}\\
{\tt bvh6@humboldt.edu}\\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: 8/12/05, Accepted: 11/18/05, Published:
11/29/05}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
We use the class equation of a finite group action together with
Burnside's orbit counting theorem to derive classical divisibility theorems.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF
  COMBINATORIAL NUMBER THEORY \smalltt 5(1) (2005), \#A26\hfill}

\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt


\section*{\normalsize 1. Introduction}

Numerous authors (see \cite{Anderson,Golomb,Hausner,Levine,Mckay} for
example) have
shown how one may deduce
classical theorems in elementary number theory and group theory using
various counting arguments. In
\cite{Anderson} and \cite{Hausner} the authors show how
one may derive Fermat's
(little), Lucas's and Wilson's theorems as well as Cauchy's theorem
for groups all from the following theorem. 
\begin{theorem}\label{combinatorial} 
  If $X$ is a finite set, $p$ a prime integer and
  $f:X\to X$ a mapping satisfying $f^p(x)=x$ for all $x\in X$, then
  $|X|\equiv|X^0|\pmod p$, where $X^0$ denotes the set of fixed points of
  $f$.
\end{theorem} 
This theorem, or rather its proof, is essentially the main idea in
\cite{Golomb} and \cite{Mckay} as well.
In \cite{Levine}, the author uses iterates of a certain complex
valued function to derive a more general divisibility
theorem (Theorem~\ref{levine} below)
for which Fermat's little theorem is the special case of a
prime divisor.

The purpose of this note is to show that Theorems~\ref{combinatorial}
and  \ref{levine} are both simple consequences
of the class equation of a cyclic group action.  Consequently,
 all of the arguments in \cite{Anderson,Golomb,Hausner,Levine,Mckay}
 are unified by
 the theory of finite group actions. In addition to putting this
 robust theory at our disposal,
this point of view also has the advantage of generalizing to non-cyclic
 actions. 
 We will illustrate these points by applying Burnside's theorem to the
 action in \cite{Levine} to derive two more 
divisibility theorems (Theorems~\ref{mine} and \ref{mine2} below) 
undetected by the method in \cite{Levine}. Just
as with Theorem~\ref{levine}, Fermat's little theorem is a special
case of Theorem~\ref{mine}, as is a well known identity involving the
 Euler $\phi$-function. We then give some famous
 examples of this technique in group theory and
 conclude with a proof of Wilson's theorem in which
 the group action is by a non-cyclic group.

\vskip 30pt

\section*{\normalsize 2. The Class Equation}

Let $X$ be a non-empty
finite set with $|X|$ elements and let $\Aut(X)$ denote the group of
permutations of $X$. If $G$ is a group, then an action of $G$
on $X$ is a homomorphism $G\to\Aut(X)$.  For each $x\in
X$, let $Gx=\{gx | g\in G\}$ and $G_x=\{g\in G | gx=x\}$ denote the
orbit of $x$ and the stabilizer of $x$ in $G$ respectively so that 
if $G$ is finite $|Gx|=(G:G_x)$ is a divisor of $|G|$.
The class equation of the action is
\begin{equation}\label{classeqn}
|X|=|X^G|+\sum_{i=1}^r |Gx_i|,
\end{equation}
where $X^G$ is the set of fixed points under the action and
$Gx_1,\dots, Gx_r$ are the distinct non-trivial orbits. If $p$ is a
prime integer and $G$ is a $p$-group
(that is, $G$ is a finite group of order $p^n$
for some integer $n\ge 1$), then the class equation (\ref{classeqn})
implies the number of
elements in $X$ is congruent to the
number of fixed points of the action modulo $p$.  That is
\begin{equation}
\label{fact} |X|\equiv |X^G|\pmod p. 
\end{equation}
Theorem~\ref{combinatorial} follows immediately from (\ref{fact}).
That is, for $X$, $p$ and $f$ as in the theorem, the map
$\Z_p\to \Aut(X)$ defined by
$1\mapsto f$ gives an action of $\Z_p$ on $X$, where $\Z_p$ denotes
the cyclic group of integers under addition modulo $p$.  Clearly $X^{\Z_p}=X^0$
so that applying (\ref{fact}) proves Theorem~\ref{combinatorial}.

\vskip 30pt


\section*{\normalsize 3. Generalizations of Fermat's Little Theorem}

In \cite{Levine}, the author uses iterates of complex function $f(z)=z^k$,
where $k$ is a fixed positive integer along with M\"obius inversion to
derive the following generalization of Fermat's little theorem.

\begin{theorem} 
\label{levine}
For any two positive integers $n$ and $k$, $n$ divides
\begin{equation*}\label{levinepoly}
P(k,n)=\sum_{d|n}\mu\left( \frac{n}{d}\right ) k^d
\end{equation*}
where $\mu$ is the M\"obius function.
\end{theorem}
If $k>1$, the argument in \cite{Levine} shows
for each integer
$n\ge 1$, $\Z_n$ acts on the set $P_n$ 
of all complex numbers $z$ for which $n$ is the smallest positive
integer satisfying $f^n(z)=z$ via the mapping $\Z_n\to
\Aut(P_n)$ given by $1\mapsto f$.  Moreover, the stabilizer of any
point $z\in P_n$ is easily seen to be trivial so that by the class
equation (\ref{classeqn}), $n||P_n|$. (If $k=1$, then $P_1$ is the set
of all complex numbers and $P_n=\emptyset$ if $n>1$.  We redefine
$P_1=\{0\}$ in this case so that we have $n||P_n|$ for all positive
$k$ and $n$.)  This is the divisibility
statement in Theorem~\ref{levine}. To express
$|P_n|$ in terms of $k$, note that $1\mapsto f$ also gives an
action of $\Z_n$ on the set $X_n$ of those
complex numbers $z$ for which $f^n(z)=z$. (If $k=1$, we take
$X_n=\{0\}$ for all $n>0$ so that $|X_n|=k^n$ for all $k,n>0$.)
Moreover, $X_n$ is a
disjoint union of the (sub-$\Z_n$) sets $P_d$, where $d$ is a positive
divisor of $n$ so that $k^n=\sum_{d|n} |P_d|$. The M\"obius 
inversion formula
is then employed to find $|P_n|$ in terms of $k$ completing
the proof of Theorem~\ref{levine}. If
$n=p$ is a
prime integer, then Theorem~\ref{levine} reduces to Fermat's
little theorem.  A detailed history of Theorem~\ref{levine} can be
found in \cite{Dickson}.

Giving an argument such as the one in \cite{Levine} from this point
of view is not just a matter of semantics. The above argument (for
$k>1$) shows that $|P_n|/n$ is the number of
orbits in the action of $\Z_n$ on
$P_n$, and since Burnside's theorem\footnote{For convenience, we
  recall that Burnside's theorem states if $G$ is a finite group acting
  on a finite set $X$ and $r$ denotes the number of distinct orbits, then
\[r=\frac{1}{|G|}\left(\sum_{g\in G} |X^g|\right )\]
where for each $g\in G$, $X^g=\{x\in X | gx=x\}$.}
 also calculates this number, it is
natural
to apply it to the action of $\Z_n$ on $X_n$ as well.
If $z\in X_n$, then for all
$j=1,\dots, n$, $f^j(z)=z$ if and only if
$f^{(j,n)}(z)=z$, where $(j,n)$ denotes the greatest common divisor of
  $j$ and $n$.  Therefore, the set of fixed points for $f^j$ and $f^i$
  in $X_n$ are equal if and only if $(j,n)=(i,n)$ and in this case the
  number of such fixed points is $k^{(j,n)}$.  Given a divisor
  $d$ of $n$, there are $\phi(n/d)$ elements $j$ in $\{1,\dots, n\}$
  with $(j,n)=d$,  where $\phi$ is Euler's totient function, so that applying
  Burnside's theorem gives the following. 
\begin{theorem} 
\label{mine}
For any two positive integers $n$ and $k$, $n$ divides
\begin{equation*}\label{mypoly}
X(k,n)=\sum_{d|n}\phi\left( \frac{n}{d}\right ) k^d.
\end{equation*}
\end{theorem}
If we take $n=p$ to be prime, then Theorem~\ref{mine} reduces to
Fermat's little theorem.  If we take $k=1$, then clearly the number of
orbits is also 1 and we recover the identity
$\sum_{d|n}\phi(d)=n$.  Theorem~\ref{mine} was first shown in
\cite{MacMahon}.  

We can say more.  Since $P_n$ is a
sub-$\Z_n$ set of $X_n$, the orbits in $P_n$ are among the orbits in
$X_n$.  That is, we should expect $X(k,n)$ to be a sum
of $P(k,n)$ and another expression $Q(k,n)$, where
$Q(k,n)/n$ is the number of orbits in the set
$Q_n=X_n-P_n$. Using the identity $\phi(n)=\sum_{d|n}\mu(n/d)d$, we can write 
\begin{equation}\label{mobiusinv}
\sum_{d|n}\phi\left( \frac{n}{d}\right ) k^d =
\sum_{d|n}\left(\sum_{e|(n/d)}\mu\left( \frac{n}{de}\right )e \right )
k^d=
\sum_{e|n}\left(\sum_{d|(n/e)}\mu\left( \frac{n}{de}\right )k^d \right )e,
\end{equation}
and recover a third divisibility theorem.
\begin{theorem} 
\label{mine2}
For any two positive integers $n$ and $k$, $n$ divides
\begin{equation*}
Q(k,n)=\sum_{\stackrel{e\ne 1}{e|n}}\sum_{d|(n/e)}\mu
\left( \frac{n}{de}\right )k^d e.
\end{equation*}
\end{theorem}
Since $X(k,n)=P(k,n)+Q(k,n)$, any two of
Theorems~\ref{levine},\ \ref{mine} or \ref{mine2} imply the third.
In fact, equation (\ref{mobiusinv}) shows that Theorem~\ref{levine} implies
Theorem~\ref{mine} directly. 

\begin{remark}
Fermat's little theorem can be derived from (the class equation of) an
action by a cyclic group
of prime order as in \cite{Hausner}, 
and once again applying Burnside's theorem to this action
gives the same divisibility result. By considering the
corresponding action by an arbitrary finite cyclic group, we 
obtain another proof of
Theorem~\ref{mine}.
Namely, if $k$ and $n$ continue to denote positive integers and we
let $A=\{1,\dots,k\}$, then
$\Z_n$ acts on the product
$X=A^n$ by cyclically permuting the coordinates of elements $x\in X$. 
Every element $g\in\Z_n$ has order $n/d$ for some divisor $d$
of $n$ and there are exactly $\phi(n/d)$ such elements each
of which fixes $k^d$ elements of $X$. Therefore
\[\sum_{g\in\Z_n}|X^g|=\sum_{d|n}\phi\left (\frac{n}{d}\right ) k^d=X(k,n).\]
By Burnside's theorem, the
number of orbits in the action is therefore
$X(k,n)/n$ and hence $n|X(n,k)$.  
\end{remark}

\vskip 30pt


\section*{\normalsize 4. More Examples}

Examples of proofs using (\ref{fact}) in elementary group theory are
abundant. The usual argument for showing the center of a $p$-group is
non-trivial uses (\ref{fact}) with the group acting on itself by
conjugation.
The $\Z_2$ action of inversion on a group of
even order shows the existence of an element of order $2$. More
generally, 
a famous application of (\ref{fact}) is McKay's elegant proof of
Cauchy's theorem for groups \cite{Mckay}. The cyclic actions here
are induced by a function as in Theorem~\ref{combinatorial}. A
beautiful line of
argumentation credited to R.~J.~Nunke in
\cite{Hungerford} uses
(\ref{fact}) repeatedly 
to establish the three Sylow theorems.

We conclude with a (non-cyclic) group action proof of Wilson's
theorem: if $p$ is a prime integer, then $(p-1)!\equiv -1\pmod p$.
Let $G=S_p$ denote the
symmetric group on
$p$ letters, and  $s\in G$
be the $p$-cycle defined by $s=(1,2,\dots,p)$.  Note that $x=\langle
s\rangle$ is a Sylow $p$-subgroup of $G$.
 Let $X$ denote the set of all subgroups of $G$ and let
$G$ act on $X$ by conjugation.  Then the stabilizer of $x\in X$ 
is the normalizer $N=N(x)$ of $x$. It is easy to show, using the fact
that any two $p$-cycles in $G$ are conjugate, that $|N|=p(p-1)$. Now,
using the Sylow theorems (and hence equation (\ref{fact})), the size of
orbit $Gx$ in $X$ satisfies
\[|Gx|\equiv 1 \pmod p.\]
We also have that 
\[|Gx|=(G:N)=\frac{|G|}{|N|}=\frac{p!}{p(p-1)}=(p-2)!,\]
and Wilson's theorem follows.
\vskip 30pt

\begin{thebibliography}{1}

\bibitem{Anderson}
Peter~G. Anderson, Arthur~T. Benjamin, and Jeremy~A. Rouse.
\newblock Combinatorial proofs of {F}ermat's, {L}ucas's and {W}ilson's
  theorems.
\newblock {\em Amer. Math. Monthly}, 112(3):266--268, March 2005.

\bibitem{Dickson}
L.~E. Dickson.
\newblock {\em History of the Theory of Numbers}, volume~1.
\newblock Carnegie Institution of Washington, Washington, D.C., 1919.

\bibitem{Golomb}
S.~W. Golomb.
\newblock Combinatorial proof of {F}ermat's little theorem.
\newblock {\em Amer. Math. Monthly}, 63(10):718, December 1956.

\bibitem{Hausner}
Melvin Hausner.
\newblock Applications of a simple counting technique.
\newblock {\em Amer. Math. Monthly}, 90(2):127--129, February 1983.

\bibitem{Hungerford}
Thomas Hungerford.
\newblock {\em Algebra}.
\newblock Springer-Verlag, New York, 1974.

\bibitem{Levine}
Lionel Levine.
\newblock Fermat's little theorem: A proof by function iteration.
\newblock {\em Mathematics Magazine}, 72(4):308--309, October 1999.

\bibitem{MacMahon}
P.A. MacMahon.
\newblock Applications of the theory of permutations in circular procession to
  the theory of numbers.
\newblock {\em Proc. London Math. Soc.}, 23:305--313, 1891-2.

\bibitem{Mckay}
James~H. McKay.
\newblock Another proof of {C}auchy's group theorem.
\newblock {\em Amer. Math. Monthly}, 66(2):119, February 1959.

\end{thebibliography}

\end{document}

% LocalWords:  Arcata Axx Lucas's Gx gx obius totient de Sylow