\documentclass[12pt]{article}%{amsart}
\usepackage{amsmath, amsfonts, amssymb, amsthm}
\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 

\def\floor #1{\left\lfloor{#1}\right\rfloor}
\def\Z{\mathbb Z}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem*{Ack}{Acknowledgment}
\theoremstyle{remark}
\newtheorem*{Rem}{Remark}

\makeatletter %% this should really go into a style file!

\renewcommand\section{\@startsection {section}{1}{\z@}%
                                 % {-3.5ex \@plus -1ex \@minus -.2ex}%
        % here is your vskip of 30pt:
                                   {-30pt  \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
        % add a point after section numbers:

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad}

\makeatother


\begin {document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A04}
\vskip 40pt

%\title{Note on a congruence involving products of binomial coefficients}
%\author{Ping Xu$^1$}
%\address{${}^1$Department of Mathematics, Nanjing University,
%Nanjing 210093, People's Republic of China}
%\email{pingxu\_nju@yahoo.com.cn}
%\author{Hao Pan$^2$}
%\address{${}^2$Department of Mathematics, Shanghai Jiaotong University,
%Shanghai 200240, People's Republic of China}
%\email{haopan79@yahoo.com.cn}
%\subjclass[2000]{Primary 11A07; Secondary 11A25} \maketitle
%\begin{abstract}

\begin{center}
\uppercase{\bf Note on a congruence involving products of binomial
coefficients}
\vskip 20pt
{\bf Ping Xu}\\
{\smallit Department of Mathematics, Nanjing University,
Nanjing 210093, People's Republic of China}\\ 
{\tt pingxu\_nju@yahoo.com.cn}\\
\vskip 10pt
{\bf Hao Pan}\\
{\smallit Department of Mathematics, Shanghai Jiaotong University,
Shanghai 200240, People's Republic of China}\\ 
{\tt haopan79@yahoo.com.cn}\\
\end{center}
\vskip 20pt
\centerline{\smallit Received: 6/30/06, Revised: 1/4/07,
 Accepted: 1/18/07,
 Published: 1/31/07}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
We prove that for integers $n, m\geqslant 2$ with $(n,2m)=1$,
\begin {equation*}
(-1)^\frac{\phi(n)(m-1)}{2}\prod\limits_{k=1}^{m-1}\prod\limits_{d|n}\binom{d-1}{[dk/m]}^{\mu(n/d)}
\equiv m(m^{\phi(n)}-1)+1 \pmod {n^2},
\end {equation*}
where $\phi(n)$ is the Euler totient function. This generalizes a
result of Granville.

%\end{abstract}

\pagestyle{myheadings}
\markright{\smalltt INTEGERS:\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY
\smalltt 7 (2007),\#A04\hfill}

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


\noindent
{\bf The Main Result}

As early as 1895, Morley \cite{morley} proved a beautiful congruence as follows:
\begin {equation}
(-1)^{(p-1)/2}\binom{p-1}{(p-1)/2}\equiv 4^{p-1}\pmod{p^3},
\end{equation}
where $p\geqslant 5$ is a prime. In \cite{granville}, Granville extended the result
of Morley and showed that
\begin {equation}
\label{gc}
(-1)^\frac{(p-1)(m-1)}{2}\prod_{k=1}^{m-1}\binom{p-1}{\floor{pk/m}}\equiv
m^p-m+1 \pmod{p^2}
\end {equation}
for any prime $p\geqslant 3$ and $m\geqslant 2$, where $\floor{x}$
denotes the greatest integer not exceeding $x$. For further
extensions of Granville's result, the reader may refer to
\cite{sun}. A $q$-analogue of (\ref{gc}) has been established in
\cite{pan}.

With the help of a generalization of Lehmer's
congruence, Cai \cite{cai} proved that
\begin {equation}
\label{cc}
(-1)^{\phi(n)/2}\prod_{d\mid
n}\binom{d-1}{(d-1)/2}^{\mu(n/d)}\equiv 4^{\phi(n)}\begin{cases}
\pmod{n^3}\quad&\text{if }3\nmid n,\\
\pmod{n^3/3}\quad&\text{if }3\mid n,
\end{cases}
\end {equation}
for any odd positive integer $n$, where $\phi(n)$ is the Euler
totient function. Inspired by Cai's result, in this note we 
generalize Granville's congruence (\ref{gc}) to arbitrary
integers $n, m\geqslant 2$ with $(n, 2m)=1$.
\begin{theorem}
\label {thm}
For any integers $n, m\geqslant 2$ with $(n,2m)=1$, we have
\begin {equation*}
(-1)^\frac{\phi(n)(m-1)}{2}\prod_{k=1}^{m-1}\prod_{d\mid n}\binom{d-1}{\floor{dk/m}}^{\mu(n/d)}
\equiv m(m^{\phi(n)}-1)+1 \pmod {n^2}.
\end {equation*}
\end {theorem}

\setcounter{lemma}{1}
First, we require a lemma on the quotients of Euler.
\begin{lemma}
\label{lem}
Let $n$ be a positive integer and $a$ be an integer with $(a,n)=1$. Then
\begin{equation}
\frac{a^{\phi(n)}-1}{n}\equiv
\sum_{\substack{j=1\\ (j,n)=1}}^{n-1}\frac{1}{aj}\floor{\frac{aj}{n}}
\pmod {n}.
\end{equation}
\end{lemma}

\noindent
{\it Proof.}
Let $1\leqslant r_j\leqslant n$ be the least non-negative residue
of $aj$ modulo $n$ for every $j\in\Z$. It is easy to see the set
$
\{r_j:\, 1\leqslant j\leqslant n, (j,n)=1\}
$
coincides with
$
\{j:\, 1\leqslant j\leqslant n, (j,n)=1\},
$
since if $j_1\not\equiv j_2\pmod{n}$ then $r_{j_1}\not=r_{j_2}$.
Hence
\begin {align*}
a^{\phi(n)}=&\prod_{\substack{j=1\\(j,n)=1}}^{n} \frac{aj}{j}
=\prod_{\substack{j=1\\
(j,n)=1}}^{n} {\frac{\floor{aj/n}n+r_j}{j}}
=\prod_{\substack{j=1\\ (j,n)=1}}^{n} \frac{r_j}{j}\bigg(1+\frac{\floor{aj/n}n}{r_j}\bigg)\\
=&\prod_{\substack{j=1\\
(j,n)=1}}^{n} \bigg(1+\frac{\floor{aj/n}n}{r_j}\bigg)
\equiv1+n\sum_{\substack{j=1\\
(j,n)=1}}^{n} \frac{1}{r_j}\floor{\frac{aj}{n}}\pmod {n^2}\\
\equiv&1+n\sum_{\substack{j=1\\
(j,n)=1}}^{n} \frac{1}{aj}\floor{\frac{aj}{n}}\pmod {n^2}.
\end {align*}
{\hfill$\Box$}

\begin{Rem}
When $n$ is a prime, the result of Lemma \ref{lem} was first
discovered by Lerch \cite{lerch}.
\end{Rem}
\begin {proof}[Proof of Theorem \ref{thm}]  Let
$\displaystyle
P_d=\prod\limits_{k=1}^{m-1}\binom{d-1}{\floor{dk/m}} \text{ and }
Q_d=\prod_{k=1}^{m-1}\prod_{\substack{j=1\\
(j,d)=1}}^{\floor{dk/m}}\bigg(\frac{d}{j}-1\bigg).
$
Then
%\begin{equation*}
$ \displaystyle
P_n=\prod_{k=1}^{m-1}\prod_{j=1}^{\floor{nk/m}}\bigg(\frac{n}{j}-1\bigg)
=\prod_{k=1}^{m-1}\prod_{d\mid n}\prod_{\substack{j=1\\ (n,j)=d}}^{\floor{nk/m}}\bigg(\frac{n}{j}-1\bigg)
=\prod_{d\mid n}Q_{n/d}=\prod_{d\mid n}Q_d.
$
%\end{equation*}
By using the inverse formula for the M\"{o}bius function,
%\begin {equation*}
$\displaystyle
Q_n=\prod\limits_{d|n}{P_d^{\mu(n/d)}}=\prod\limits_{d|n}
\prod\limits_{k=1}^{m-1}\binom{d-1}{\floor{dk/m}}^{\mu(n/d)}.
$
%\end {equation*}
On the other hand,
define
$\displaystyle
N=\sum_{k=1}^{m-1}|\{j:\, 1\leqslant j\leqslant \floor{nk/m},
(j,n)=1\}|
$
and apply Lemma \ref{lem} to get
\begin {align*}
(-1)^N Q_n =&\prod_{k=1}^{m-1}\prod_{\substack{j=1\\
(j,n)=1}}^{\floor{nk/m}}\bigg(1-\frac{n}{j}\bigg)
\equiv1-n\sum_{k=1}^{m-1}\sum_{\substack{j=1\\ (j,n)=1}}^{\floor{nk/m}}\frac{1}{j}\pmod{n^2}\\
=&1-n\sum_{\substack{j=1\\
(j,n)=1}}^{n-1}\frac{1}{j}\sum_{k=\floor{mj/n}+1}^{m-1}1
=1-n\sum_{\substack{j=1\\ (j,n)=1}}^{n-1}{\frac{m-1-\floor{mj/n}}{j}}\\
=&1-n(m-1)\sum_{\substack{j=1\\ (j,n)=1}}^{n-1}{\frac{1}{j}}
+nm\sum_{\substack{j=1\\(j,n)=1}}^{n-1}{\frac{\floor{mj/n}}{mj}}\\
\equiv &m(m^{\phi(n)}-1)+1\pmod{n^2},
\end {align*}
where the last congruence follows from

$$
\sum_{\substack{j=1\\
(j,n)=1}}^{n-1}{\frac{1}{j}}=\frac{1}{2}\sum_{\substack{j=1\\
(j,n)=1}}^{n-1}\bigg(\frac{1}{j}+\frac{1}{n-j}\bigg)=\frac{n}{2}\sum_{\substack{j=1\\
(j,n)=1}}^{n-1}\frac{1}{j(n-j)}\equiv0\pmod{n}.
$$
Finally,
\begin {align*}
N=&\sum_{k=1}^{m-1}\sum_{\substack{j=1\\
(j,n)=1}}^{\floor{nk/m}}{1} =\sum_{\substack{j=1\\
(j,n)=1}}^{n-1}\sum_{k=\floor{mj/n}+1}^{m-1}1
=\sum_{\substack{j=1\\ (j,n)=1}}^{n-1}\bigg(m-1-\floor{\frac{mj}{n}}\bigg)\\
=&(m-1)\phi(n)-\sum_{\substack{j=1\\ (j,n)=1}}^{n-1}\bigg(\frac{mj}{n}-\bigg\{\frac{mj}{n}\bigg\}\bigg)\\
=&(m-1)\phi(n)-\sum\limits_{\substack{j=1\\(j,n)=1}}^{n-1}\bigg(\frac{mj}{n}-\frac{j}{n}\bigg)=\frac{\phi(n)(m-1)}{2},
\end {align*}
where $\{x\}=x-\floor{x}$.
\end {proof}
\vskip 30pt
\begin{Ack} We are grateful to the anonymous referee for his/her
valuable suggestions on this paper. We also thank our advisor,
Professor Zhi-Wei Sun, for his helpful comments.
\end{Ack}





\begin{thebibliography}{99} \footnotesize

\bibitem {cai} Tianxin Cai, \emph{A congruence involving the quotients of Euler and its
applications (I)}, Acta Arith., {\bf 103}(2002).

\bibitem {granville} A. Granville, \emph{Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers},
in Organic mathematics (Burnady,BC,1995), CMS Conf. Proc., 20, Amer. Math. Soc., Providence, RI, 1997, pp. 253-276.

\bibitem {lerch} M. Lerch, \emph{Zur Theorie des Fermatschen Quotienten
$(a^{p-1}-1)/p=q(a)$}, Math. Ann., {\bf 60}(1905),471-490.

\bibitem {morley} F. Morley, \emph{Note on the congruence $2^{4n}\equiv(-1)^n(2n)!/(n!)^2$, where $2n+1$ is a prime},
Annals of Math., {\bf 9}(1895), 168-170.

\bibitem {pan} H. Pan, \emph{A $q$-analogue of Lehmer's congruence},
preprint,\\ arXiv:math.NT/0507511.

\bibitem {sun} Z.-W. Sun, \emph{Products of binomial coefficients modulo $p^2$},
Acta Arith., {\bf 97}(2001), 87-98.

\end{thebibliography}
\end {document}