Fermat Numbers in Multinomial Coefficients

Shane Chern Department of Mathematics Zhejiang University Hangzhou, 310027 China

                   chenxiaohang92@gmail.com

Abstract In 2001 Luca proved that no Fermat number can be a nontrivial binomial coefficient.

We extend this result to multinomial coefficients.

1 Introduction

Let F_{m} = 2^{2^{m}} +1 be the m^{th} Fermat number for any nonnegative integer m. Several authors studied the Diophantine equation

\binom{n}{k} = 2^{2^{m}} + 1 = F_{m},  (1)

where n ≥ 2k ≥ 2, and m ≥ 0. We refer to the articles [2, 3, 5, 6, 8] for further details. In 2001, Luca [6] completely solved Eq. (1) and proved that it has only the trivial solutions k = 1, n − 1 and n = F_{m}. The proof is mainly based on a congruence given by Lucas [7]. For more about Fermat numbers, see [4].

For a positive integer t, let n, k_{1}, …, k_{t} be nonnegative integers, and define the t-order multinomial coefficient as follows:

\binom{n}{k_{1}, …, k_{t}} = \frac{n(n − 1) ⋯ (n − k_{1} − ⋯ − k_{t} + 1)}{k_{1}! ⋯ k_{t}!},

with ∑_{i=1}^{t} k_{i} < n + 1. In particular, \binom{n}{0,...,0} = 1. Note that for t ≥ 2, if ∑_{i=1}^{t} k_{i} = n, then the t-order multinomial coefficient equals a (t − 1)-order multinomial coefficient

\binom{n}{k_{1}, …, k_{t}} = \binom{n}{k_{1}, …, k_{t−1}}.

There are many papers concerning the Diophantine equations related to multinomial coefficients. For example, Yang and Cai [9] proved that the Diophantine equation

\binom{n}{k_{1}, …, k_{t}} = x^{l}

has no positive integer solutions for n, t ≥ 3, l ≥ 2, and ∑_{i=1}^{t} k_{i} = n.

In this paper, we consider the Diophantine equation

\binom{n}{k_{1}, …, k_{t}} = 2^{2^{m}} + 1 = F_{m}, for t ≥ 2, and ∑_{i=1}^{t} k_{i} < n,  (2)

and prove the following theorem.

Theorem 1. The Diophantine equation (2) has no integer solutions (m, n, k_{1}, …, k_{t}) for nonnegative m and positive n, k_{1}, …, k_{t}.

2 Two Lemmas

To prove Theorem 1, we need the following two lemmas.

Lemma 2 (Euler [1]). Any prime factor p of the Fermat number F_{m} satisfies

p ≡ 1 (mod 2^{m+1}).

Lemma 3 (Luca [6]). If F_{m} = s\binom{n}{k}, with m ≥ 5, s ≥ 1, and 1 ≤ k ≤ \frac{n}{2}, we have the following two properties.

(i) Let n = n′d, where

A = {p : prime p | n, and p ≡ 1 (mod 2^{m+1})} ,

and

n′ = ∏_{p∈A} p^{α_{p}}.

Then k = d < 2^{m}.

(ii) k − i | n − i for any i = 0, …, k − 1.

Remark 4. Lemma 3 is summarized from Luca’s proof [6] of Diophantine equation (1). Although Luca only proved the case s = 1, he indicated that the result also holds for all positive integers s.

3 Proof of Theorem 1

The first five Fermat numbers are primes, which cannot be a multinomial coefficient in Eq. (2). Therefore, we only need to consider m ≥ 5.

Moreover, for any multinomial coefficient \binom{n}{k_{1},...,k_{t}} with t > 0, k_{1}, …, k_{t} ≥ 1, and ∑_{i=1}^{t} k_{i} < n, there exists a multinomial coefficient

\binom{n}{k′_{1}, …, k′_{t}} = \binom{n}{k_{1}, …, k_{t}},

such that 1 ≤ k′_{1}, …, k′_{t} ≤ \frac{n}{2}.

Hence, Eq. (2) becomes

F_{m} = \binom{n}{k_{1}, …, k_{t}}, for m ≥ 5, 1 ≤ k_{i} ≤ \frac{n}{2}, and ∑_{i=1}^{t} k_{i} < n.  (3)

Let n = n′d, where

A = {p : prime p | n, and p ≡ 1 (mod 2^{m+1})} ,

and

n′ = ∏_{p∈A} p^{α_{p}}.

For any i = 1, …, t, we have

F_{m} = \binom{n}{k_{1}, …, k_{t}} = \binom{n}{k_{i}}\binom{n − k_{i}}{k_{1}, …, k_{i−1}, k_{i+1}, …, k_{t}},  (4)

where \binom{n−k_{i}}{k_{1},...,k_{i−1},k_{i+1},...,k_{t}} is a positive integer. By Lemma 3 (i), we have k_{i} = d < 2^{m} for i = 1, …, t. Then Eq. (3) becomes

F_{m} = \binom{n}{\underbrace{d, …, d}_{t}}, n > td, and t ≥ 2  (5)

= \binom{n}{d}\binom{n − d}{d}\binom{n − 2d}{\underbrace{d, …, d}_{t−2}}.  (6)

Note that d ≥ 1. We study Eq. (6) in the following three cases.

Case 1: d > 2. Since n > 2d and d | n, we have n ≥ 3d. Then,

d ≤ \frac{n − d}{2} < \frac{n}{2}.

In Eq. (6), applying Lemma 3 (ii) to \binom{n}{d} and \binom{n−d}{d} respectively, and setting i = 1, we have

d − 1 | n − 1

and

d − 1 | n − d − 1.

Thus, d − 1 | d, which is impossible.

Case 2: d = 2. Let n = 2n′. Then Eq. (5) becomes

F_{m} = \binom{2n′}{\underbrace{2, …, 2}_{t}} = n′(2n′ − 1)(n′ − 1)(2n′ − 3)\binom{2n′ − 4}{\underbrace{2, …, 2}_{t−2}}.

Then n′ and n′ − 1 are both F_{m}’s factors. According to Lemma 2, we obtain n′ ≡ n′ − 1 ≡ 1 (mod 2^{m+1}), which is impossible.

Case 3: d = 1. Eq. (5) becomes

F_{m} = \binom{n}{\underbrace{1, …, 1}_{t}} = n(n − 1)\binom{n − 2}{\underbrace{1, …, 1}_{t−2}}.

Then n and n − 1 are both F_{m}’s factors. According to Lemma 2, we obtain n ≡ n − 1 ≡ 1 (mod 2^{m+1}), which is also impossible.

This completes the proof of Theorem 1.

Remark 5. One can even find that the multinomial coefficient in Eq. (2) could not divide a Fermat number. Otherwise, assume that there exists a positive integer s such that

F_{m} = s\binom{n}{k_{1}, …, k_{t}}.

Note that in Eq. (4) we still have

\binom{n}{k_{i}} | F_{m},

and in Eqs. (5) and (6) similar results hold. Hence, we can get the proof in the same way.

4 Acknowledgments

I am indebted to Mr. Yong Zhang for providing relevant references and examining the whole proof, and to Mr. Jiaxing Cui for giving detailed comments.

I am also indebted to the referee for his careful reading and helpful suggestions.

References

[1] L. Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus, Acad. Sci. Petropol. 6 (1738), 103–107. Available at

   http://eulerarchive.maa.org/pages/E026.html.

[2] D. Hewgill, A relationship between Pascal’s triangle and Fermat’s numbers, Fibonacci Quart. 15 (1977), 183–184.

[3] H. V. Krishna, On Mersenne and Fermat numbers, Math. Student 39 (1971), 51–52.

[4] M. Křížek, F. Luca, and L. Somer, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, 2001.

[5] F. Luca, Pascal’s triangle and constructible polygons, Util. Math. 58 (2000), 209–214.

[6] F. Luca, Fermat numbers in the Pascal triangle, Divulg. Mat. 9 (2001), 191–195.

[7] É. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1 (1878), 184–196, 197–240, 289–321.

[8] P. Radovici-Mărculescu, Diophantine equations without solutions (Romanian), Gaz. Mat. Mat. Inform. 1 (1980), 115–117.

[9] P. Yang and T. Cai, On the Diophantine equation \binom{n}{k_{1},...,k_{s}} = x^{l}, Acta Arith. 151 (2012), 7–9.

2010 Mathematics Subject Classification: Primary 11D61; Secondary 11D72, 05A10. Keywords: Fermat number, multinomial coefficient.

(Concerned with sequence \underline{A000215}.)

Received January 19 2014; revised version received February 11 2014. Published in Journal of Integer Sequences, February 15 2014.

Return to Journal of Integer Sequences home page.