INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A04

NOTE ON A CONGRUENCE INVOLVING PRODUCTS OF BINOMIAL COEFFICIENTS

Ping Xu

Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China

                          pingxu nju@yahoo.com.cn

Hao Pan

Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, People’s Republic of China

                           haopan79@yahoo.com.cn

Received: 6/30/06, Revised: 1/4/07, Accepted: 1/18/07, Published: 1/31/07

Abstract

We prove that for integers n, m ⩾ 2 with (n, 2m) = 1,

(−1)^{\frac{ϕ(n)(m−1)}{2}} ∏_{k=1}^{m−1} ∏_{d|n} \binom{d − 1}{[dk/m]}^{μ(n/d)} ≡ m(m^{ϕ(n)} − 1) + 1 (mod n^{2}),

where ϕ(n) is the Euler totient function. This generalizes a result of Granville.

The Main Result

As early as 1895, Morley [4] proved a beautiful congruence as follows:

(−1)^{(p−1)/2}\binom{p − 1}{(p − 1)/2} ≡ 4^{p−1} (mod p^{3}),  (1)

where p ⩾ 5 is a prime. In [2], Granville extended the result of Morley and showed that

(−1)^{\frac{(p−1)(m−1)}{2}} ∏_{k=1}^{m−1} \binom{p − 1}{⌊pk/m⌋} ≡ m^{p} − m + 1 (mod p^{2})  (2)

for any prime p ⩾ 3 and m ⩾ 2, where ⌊x⌋ denotes the greatest integer not exceeding x. For further extensions of Granville’s result, the reader may refer to [6]. A q-analogue of (2) has been established in [5].

With the help of a generalization of Lehmer’s congruence, Cai [1] proved that

(−1)^{ϕ(n)/2} ∏_{d|n} \binom{d − 1}{(d − 1)/2}^{μ(n/d)} ≡ 4^{ϕ(n)} \{ \begin{matrix}(mod n^{3}) & if 3 ∤ n, \\ (mod n^{3}/3) & if 3 | n, \end{matrix}  (3)

for any odd positive integer n, where ϕ(n) is the Euler totient function. Inspired by Cai’s result, in this note we generalize Granville’s congruence (2) to arbitrary integers n, m ⩾ 2 with (n, 2m) = 1.

Theorem 1. For any integers n, m ⩾ 2 with (n, 2m) = 1, we have

(−1)^{\frac{ϕ(n)(m−1)}{2}} ∏_{k=1}^{m−1} ∏_{d|n} \binom{d − 1}{⌊dk/m⌋}^{μ(n/d)} ≡ m(m^{ϕ(n)} − 1) + 1 (mod n^{2}).

First, we require a lemma on the quotients of Euler.

Lemma 2. Let n be a positive integer and a be an integer with (a, n) = 1. Then

\frac{a^{ϕ(n)} − 1}{n} ≡ ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{1}{aj} ⌊\frac{aj}{n} ⌋ (mod n).  (4)

Proof. Let 1 ⩽ r_{j} ⩽ n be the least non-negative residue of aj modulo n for every j ∈ ℤ. It is easy to see the set {r_{j} : 1 ⩽ j ⩽ n, (j, n) = 1} coincides with {j : 1 ⩽ j ⩽ n, (j, n) = 1}, since if j_{1} ≢ j_{2} (mod n) then r_{j_{1}} ≠ r_{j_{2}}. Hence

a^{ϕ(n)} = ∏_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n} \frac{aj}{j} = ∏_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n} \frac{⌊aj/n⌋ n + r_{j}}{j} = ∏_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n} \frac{r_{j}}{j} (1 + \frac{⌊aj/n⌋ n}{r_{j}})

= ∏_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n} (1 + \frac{⌊aj/n⌋ n}{r_{j}}) ≡ 1 + n ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n} \frac{1}{r_{j}} ⌊\frac{aj}{n} ⌋ (mod n^{2})

≡1 + n ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n} \frac{1}{aj} ⌊\frac{aj}{n} ⌋ (mod n^{2}).

□

Remark. When n is a prime, the result of Lemma 2 was first discovered by Lerch [3].

Proof of Theorem 1. Let P_{d} = ∏_{k=1}^{m−1} \binom{d − 1}{⌊dk/m⌋} and Q_{d} = ∏_{k=1}^{m−1} ∏_{\begin{matrix}j=1 \\ (j,d)=1 \end{matrix}}^{⌊dk/m⌋} (\frac{d}{j} − 1). Then P_{n} =

∏_{k=1}^{m−1} ∏_{j=1}^{⌊nk/m⌋} (\frac{n}{j} − 1) = ∏_{k=1}^{m−1} ∏_{d|n} ∏_{\begin{matrix}j=1 \\ (n,j)=d \end{matrix}}^{⌊nk/m⌋} (\frac{n}{j} − 1) = ∏_{d|n} Q_{n/d} = ∏_{d|n} Q_{d}. By using the inverse

formula for the Möbius function, Q_{n} = ∏_{d|n} P_{d}^{μ(n/d)} = ∏_{d|n} ∏_{k=1}^{m−1} \binom{d − 1}{⌊dk/m⌋}^{μ(n/d)}. On the other

hand, define N = ∑_{k=1}^{m−1} |{j : 1 ⩽ j ⩽ ⌊nk/m⌋ , (j, n) = 1}| and apply Lemma 2 to get

(−1)^{N}Q_{n} = ∏_{k=1}^{m−1} ∏_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{⌊nk/m⌋} (1 − \frac{n}{j}) ≡ 1 − n ∑_{k=1}^{m−1} ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{⌊nk/m⌋} \frac{1}{j} (mod n^{2})

=1 − n ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{1}{j} ∑_{k=⌊mj/n⌋+1}^{m−1} 1 = 1 − n ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{m − 1 − ⌊mj/n⌋}{j}

=1 − n(m − 1) ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{1}{j} + nm ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{⌊mj/n⌋}{mj}

≡m(m^{ϕ(n)} − 1) + 1 (mod n^{2}),

where the last congruence follows from

∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{1}{j} = \frac{1}{2} ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} (\frac{1}{j} + \frac{1}{n − j} ) = \frac{n}{2} ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} \frac{1}{j(n − j)} ≡ 0 (mod n).

Finally,

N = ∑_{k=1}^{m−1} ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{⌊nk/m⌋} 1 = ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} ∑_{k=⌊mj/n⌋+1}^{m−1} 1 = ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} (m − 1 − ⌊\frac{mj}{n} ⌋ )

=(m − 1)ϕ(n) − ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} (\frac{mj}{n} − \{\frac{mj}{n} \})

=(m − 1)ϕ(n) − ∑_{\begin{matrix}j=1 \\ (j,n)=1 \end{matrix}}^{n−1} (\frac{mj}{n} − \frac{j}{n}) = \frac{ϕ(n)(m − 1)}{2},

where {x} = x − ⌊x⌋.

Acknowledgment. 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.

References

[1] Tianxin Cai, A congruence involving the quotients of Euler and its applications (I), Acta Arith., 103(2002).

[2] A. Granville, 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.

[3] M. Lerch, Zur Theorie des Fermatschen Quotienten (a^{p−1}−1)/p = q(a), Math. Ann., 60(1905),471-490.

[4] F. Morley, Note on the congruence 2^{4n} ≡ (−1)^{n}(2n)!/(n!)^{2}, where 2n + 1 is a prime, Annals of Math., 9(1895), 168-170.

[5] H. Pan, A q-analogue of Lehmer’s congruence, preprint, arXiv:math.NT/0507511.

[6] Z.-W. Sun, Products of binomial coefficients modulo p^{2}, Acta Arith., 97(2001), 87-98.