ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 297-309 https://doi.org/10.26493/1855-3974.2103.e84
(Also available at http://amc-journal.eu)
On the divisibility of binomial coefficients
Silvia Casacuberta * ©
Harvard University, 1 Oxford Street, Cambridge, MA, USA
Received 30 August 2019, accepted 16 August 2020, published online 18 November 2020
Shareshian and Woodroofe asked if for every positive integer n there exist primes p and q such that, for all integers k with 1 < k < n - 1, the binomial coefficient (k) is divisible by at least one of p or q. We give conditions under which a number n has this property and discuss a variant of this problem involving more than two primes. We prove that every positive integer n has infinitely many multiples with this property.
Keywords: Binomial coefficients, divisibility, primorials. Math. Subj. Class. (2020): 11B65, 05A10
1 Introduction
Binomial coefficients display interesting divisibility properties. Conditions under which a prime power pa divides a binomial coefficient (k) are given by Kummer's Theorem [10] and also by a generalized form of Lucas' Theorem [5, 13].
Still, there are problems involving divisibility of binomial coefficients that remain unsolved. In this article we investigate the following question, which was asked by Shareshian and Woodroofe in [16].
Question 1.1. Is it true that for every positive integer n there exist primes p and q such that, for all integers k with 1 < k < n — 1, the binomial coefficient (k) is divisible by p or q?
As in [16], we say that n satisfies Condition 1 if such primes p and q exist for n. In this article we discuss sufficient conditions under which an integer n satisfies Condition 1. In Sections 2 and 3 we prove a variation of the Sieve Lemma from [16] and use it to show that
*I am indebted to my mentor Oscar Mickelin for his guidance throughout this research and to Prof. Russ Woodroofe for correspondence and kind suggestions. This work was carried out during the Research Science Program at MIT in the summer of 2017 and was supported by the Center for Excellence in Education, the MIT Mathematics Department, and the Youth and Science Program of Fundacio Catalunya La Pedrera (Barcelona). E-mail address: scasacubertapuig@college.harvard.edu (Silvia Casacuberta)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
297
Ars Math. Contemp. 19 (2020) 189-208
n satisfies Condition 1 if certain inequalities hold. In Section 5 we infer that every positive integer has infinitely many multiples for which Condition 1 is satisfied.
The collection of numbers for which Condition 1 is not known to hold has asymptotic density 0 assuming the truth of Cramer's conjecture (as first shown in [16]) and includes most primorials • • • Pi, where pi,..., pi are the first i primes, namely those primorials such that (pip2 • • • pi) - 1 is not a prime.
In addition, we introduce the following variant of Condition 1:
Definition 1.2. A positive integer n satisfies the N-variation of Condition 1 if there exist N different primes pi;..., pN such that if 1 < k < n - 1 then (k) is divisible by at least one of pi,... ,pN.
For example, it follows from Kummer's Theorem or from Lucas' Theorem that a positive integer n satisfies the 1-variation of Condition 1 if and only if n is a prime power, and every integer n satisfies the m-variation of Condition 1 if n = p^1 • • • p^T where pi;..., pm are distinct primes. In Section 4 we discuss upper bounds on N so that a given n satisfies the N-variation of Condition 1.
2 An extended Sieve Lemma
Our results in this section will be based on Lucas' Theorem: Theorem 2.1 (Lucas [13]). Let p be a prime and let
n = nr pr + nr-ipr-i + • • • + nip + no k = kr pr + kr-ipr-i + • • • + kip + ko
be base p expansions of two positive integers, where 0 < ni < p and 0 < ki < p for all i, and nr = 0. Then
'n)s n (kij p).
By convention, a binomial coefficient (k*) is zero if ni < ki. Hence, if any of the digits of the base p expansion of n is 0 whereas the corresponding digit in the base p expansion of k is nonzero, then (k) is divisible by p. A s a particular case, if a prime power pa with a > 0 divides n and does not divide k, then (k) is divisible by p.
Observe that, if n satisfies Condition 1 with two primes p and q, then at least one of these primes has to be a divisor of n, because otherwise (i) would not be divisible by any of them. The next two results are elementary consequences of Lucas' Theorem.
Proposition 2.2. If n = pa + 1 with p a prime and a > 0, then n satisfies Condition 1 with p and any prime dividing n.
Proof. If n -1 is a prime power then the two summands in the left-hand term of the equality
n - 1	n - 1	n
k - 1 + k = k
are divisible by p by Lucas' Theorem if 2 < k < n - 2, and hence (k) is also divisible by p. If k =1 or k = n - 1, then (k) = n, so any prime factor of n divides (k).	□
S. Casacuberta: On the divisibility of binomial coefficients
299
Proposition 2.3. If a positive integer n is equal to the product of two prime powers pf and p2 with a > 0, b > 0, and pi = p2, then n satisfies Condition 1 with pi and p2.
Proof. The base p1 expansion of n ends with a zeroes and the base p2 expansion of n ends with b zeroes. Because a positive integer k smaller than n cannot be divisible by both pf and p2, it is not possible that k ends with a zeroes in base p1 and b zeroes in base p2. Consequently, we can apply Lucas' Theorem modulo p1 if pf does not divide k or modulo p2 if p2 does not divide k.	□
Proposition 2.3 generalizes as follows.
Proposition 2.4. If p1;... ,pm are distinct primes and n = pf1 • • • pm with aj > 0 for all i, then n satisfies the m-variation of Condition 1 with p1... ,pm.
Proof. If 1 < k < n - 1, then the base pj expansion of k ends with less zeroes than the base pj expansion of n for at least one prime factor pj of n.	□
The following result extends [16, Lemma 4.3]. It is the starting point of our discussion of Question 1.1 in the next sections. By symmetry, we only need to consider those values of k with k < n/2. Moreover, we may restrict our study further to those values of k that are multiples of pf, since otherwise (k) is divisible by p.
Theorem 2.5. Let n be a positive integer and suppose that pf divides n where p is a prime and a > 0. Suppose that there is a prime q with n/(d +1) < q < n/d, where d > 1, and let k n /2. Then (£) is divisible by p or q except possibly when k is a multiple ofpf belonging to one of the intervals [cq, cq + p] with P = n — dq and 0 < c < (d + 1)/2.
Proof. Since q < n/d, the number p = n — dq is positive. If k < p then k is in the interval [0, p], which is the case c = 0 in the statement of the theorem.
The assumption that n/(d +1) < q is equivalent to assuming the inequality n — dq < q, which implies that the last digit in the base q expansion of n is equal to p. Hence, if P < k < q then we may infer from Lucas' Theorem that (k) is divisible by q.
The remaining range of values of k to be considered is q < k < n/2. In this case we look at the last digit of the base q expansion of k. If this last digit is bigger than p, then (k) is again divisible by q. Thus the undecided cases are those in which the residue of k modulo q is smaller than or equal to p. This happens when cq < k < cq + p for some positive integer c, and if cq < k < n/2 then c < n/(2q) < (d + 1)/2.	□
By the Bertrand-Chebyshev Theorem [2], for every integer n > 2 there exists a prime q such that n/2 < q < n. This yields the following particular instance of Theorem 2.5, which is also a special case of [16, Lemma 4.3].
Corollary 2.6. For a positive integer n, suppose that pf divides n where p is a prime and a > 0. If q is a prime such that n/2 < q < n and n — q < pf, then n satisfies Condition 1 with p and q.
Proof. Pick d =1 in Theorem 2.5.	□
Note that, under the assumptions of Corollary 2.6, the equality n — q = pf cannot hold, since p divides n and p = q because q does not divide n. Hence there remains to study the case when n — q > pf and q is the largest prime smaller than n while pf is the largest
300
Ars Math. Contemp. 19 (2020) 189-208
prime power dividing n. In other words, Condition 1 holds for n whenever there is a prime between n — pa and n.
The sequence of integers n for which there is no prime between n — pa and n can be found in the On-Line Encyclopedia of Integer Sequences (OEIS) [17] with the reference A290203 [3]. Its first terms are the following:
126, 210, 330, 630,1144,1360, 2520, 2574, 2992, 3432, 3960, 4199,... (2.1)
Banderier's conjecture [1] claims that if pn# denotes the n-th primorial, that is,
Pn# = PlP2 • • • Pn
where p1,...,pn are the first n primes, and q is the largest prime below pn#, then either
Pn# — q =1 orp„# — q is a prime.
Proposition 2.7. If Banderier's conjecture is true, then the sequence (2.1) contains all primorials pn# such that pn# — 1 is not a prime.
Proof. If pn# — 1 is not a prime, then pn# — q is a prime according to Banderier's conjecture. Since pn# — q does not divide pn#, we infer that pn# — q is bigger than pn, which is the largest prime power dividing pn #.	□
The first primorials pn# such that pn# — 1 is not a prime are
p4 # = 210, p7 # = 510510, p8# = 9699690, p9# = 223092870.
Inspecting this list could be a strategy to seek for a counterexample for Question 1.1. The complementary list of primorials can be found in OEIS with reference A057704 [11].
For any fixed value of d, the number fi in Theorem 2.5 is smallest when q is as close as possible to n/d. For this reason, we focus our attention on the largest prime qd below n/d for various values of d. This motivates the next definition.
Definition 2.8. For positive integers n and 1 < d < n/2, let qd be the largest prime smaller than n/d and let = n — dqd. For each integer c with 0 < c < (d +1)/2, we call [cqd, cqd + a dangerous interval.
By Theorem 2.5, if we attempt to prove that Condition 1 holds with p and qd assuming that qd > n/(d + 1) —that is, assuming that the dangerous intervals are disjoint— we only need to care about values of k that lie in a dangerous interval and are multiples of the largest power of p dividing n.
In the case d =1, the only dangerous interval below n/2 is [0, n — q1]. When d =2, we have that [0, n — 2q2] and [q2, n — q2] are dangerous intervals. Since n — q2 > n/2, the second interval may be replaced by [q2, n/2] to carry our study further, as we do in the next section.
Example 2.9. The largest prime below n = p7# = 510510 is qi = 510481 and the largest prime dividing n is p = 17. Here n — q1 = 29 and therefore (k) is divisible by 17 or 510481 for all k except for k =17.
S. Casacuberta: On the divisibility of binomial coefficients
301
On the other hand, the largest prime below n/2 = 255255 is q2 = 255253. Thus = n — 2q2 =4 and therefore [0,4] and [255253, 255257] are dangerous intervals. The second interval contains a multiple of 17, namely n/2. However, since
510510 = 6 • 174 + 1 • 173 + 15 • 172 + 8 • 17, 255255 = 3 • 174 + 0 • 173 + 16 • 172 +4 • 17,
we infer from Lucas' Theorem that (250210) is divisible by 17. Consequently, (k) is divisible by 17 or 255253 for all k.
3 Using the nearest prime below n/2
Nagura showed in [14] that, if m > 25, then there is a prime between m and (1 + 1/5)m. Therefore, there is a prime q such that 5n/6 < q < n when n > 30. This implies that, if n > 30 and the largest prime-power divisor pa of n satisfies pa > n/6, then there is a prime q between n — pa and n and hence Condition 1 holds for n with p and q. The following result is sharper.
Proposition 3.1. If n > 2010882 and the largest prime-power divisor pa of n satisfies pa > n/16598, then n satisfies Condition 1 with p and the nearest prime q below n.
Proof. Schoenfeld proved in [15] that for m > 2010760 there is a prime between m and (1 + 1/16597)m. Hence, if n > 2010882 and the largest prime-power divisor pa of n satisfies pa > n/16598 then there is a prime between n — pa and n, and therefore Condition 1 holds for n by Corollary 2.6.	□
The following are consequences of Nagura's and Schoenfeld's bounds.
Lemma 3.2. Let qd be the largest prime below n/d for positive integers n and d.
(a)	If n > 120 and d < 5, then n/(d +1) < qd.
(b)	If n > 3.34 • 1010 and d < 16597, then n/(d +1) < qd.
Proof. By Nagura's bound [14], if n/d > 30, then 5n/6d < qd < n/d. Therefore, n — dqd < n/6. If d < 5, then 6d < 5(d + 1) and hence
5n(d + 1)
n < 6d < qd(d +1),
as claimed. The proof of part (b) is analogous using Schoenfeld's bound [15].	□
In order to apply Theorem 2.5 with d = 2 for a given n, we need that there is a prime q such that n/3 < q < n/2. If q2 denotes the nearest prime below n/2, then the inequality n/3 < q2 holds if n > 120 by Lemma 3.2. Since by (2.1) we have that n — q1 < pa if n < 126, we may assume that n/3 < q2 without any loss of generality.
Note that the inequality n/3 < q is equivalent to n — 2q < q, so the intervals [0, n — 2q] and [q, n — q] are disjoint.
Theorem 3.3. For an odd positive integer n and a prime power pa dividing n, suppose that there is a prime q with n/3 < q < n/2 and n — 2q < pa. Then n satisfies Condition 1 with p and q.
302
Ars Math. Contemp. 19 (2020) 189-208
Proof. By Theorem 2.5, in order to infer that (k) is divisible by p or q, the only cases that we need to discuss are those values of k that are multiples of p° with k e [0, n - 2q] or k e [q, n—q]. By assumption, there are no multiples ofp° in [0, n—2q]. Since n —q > n/2, we may focus on the interval [q, n/2]. Since n is odd, n/2 is not an integer; hence we are only left to prove that there is no multiple k of p° with q < k < n/2. We will prove this by contradiction.
Thus suppose that q < Ap° < n/2 for some integer A. The assumption that n — 2q < p° implies that n — p° < 2q and hence
n/2 — p°/2 < q < Ap°.
Consequently, Ap° < n/2 < (A + 1/2)p°. If we now write n = mpa, we obtain that 2A < m < 2A +1, which is impossible for an integer m.	□
The rest of this section is devoted to the case when n is even.
Lemma 3.4. Suppose that n is even and there is a prime q with q < n/2 and n — 2q < p°, where p° is the largest power of p dividing n. If there is a multiple k of p° in the interval [q, n/2], then p is odd and k = n/2.
Proof. Suppose first that p is odd. Then the integer n/2 is a multiple of p°, so we may write n/2 = Ap° for some integer A. If there is another multiple of p° in the interval [q, n/2], then q < (A — 1)p° < n/2, and this implies that
n/2 — p° = Ap° — p° = (A — 1)p° > q.
Hence n — 2q > 2p°, which is incompatible with our assumption that n — 2q < p°.
In the case p =2 (so that 2° is the largest power of 2 dividing n), we have that n/2 is divisible by 2°-1, and we may write n/2 = A2°-1 with A odd. If there is a multiple of 2° in the interval [q, n/2), then q < < n/2, so ^ < A/2 and ^ < (A — 1)/2 because A is odd. Therefore
n/2 — 2°-1 = (A — 1)2°-1 > > q. Hence, as above, n — 2q > 2°, which contradicts that n — 2q < 2°.	□
Theorem 3.5. For an even positive integer n, suppose that there is a prime q such that n/3 < q < n/2 and n — 2q < p°, where p° is the largest power ofp dividing n.
(a)	Ifp = 2, then n satisfies Condition 1 with 2 and q.
(b)	If p = 2, then n satisfies Condition 1 with p and q if and only if (n/2) is divisible by p.
Proof. By Theorem 2.5 and Lemma 3.4, the only case left is k = n/2 for p odd. Consequently, if (n/2) is divisible by p, then n satisfies Condition 1 with p and q. Moreover, (n/2) is not divisible by q, since the base q expansions of n and n/2 are, respectively,
2 • q + (n — 2q) and 1 • q + (n/2 — q). Hence the assumption that (n/2) be divisible by p is necessary.	□
S. Casacuberta: On the divisibility of binomial coefficients
303
Our last remarks in this section correspond to the case when n is even, and they are only relevant if p = 2, by Theorem 3.5. Next we give sufficient conditions to infer that a prime p divides (nJ2). The greatest integer less than or equal to a real number x is denoted by |_xj, and we write vp(n) = a if pa is the maximum power of p such that pa divides n.
Recall from [12] that
>(n!) = E
k= 1
- sp(n) p — 1 '
(3.1)
where sp(n) denotes the sum of all the digits in the base p expansion of n.
Proposition 3.6. Suppose that n is even. A prime p divides (nJ2) if and only if at least one of the numbers |_n/pr J with r > 1 is odd.
Proof. By comparing vp(n!) and vp((n/2)!) we see that, for each r,
n	=2	n/2
pr		pr
if |_n/prJ is even. If |_n/prJ is even for all r, we conclude that vp(n!) = 2vp((n/2)!), and hence p does not divide (n„2). However, if |_n/pr J is odd, then
n	=2	n/2
pr		pr
+ 1
□
□
and consequently vp(n!) is greater than 2vp((n/2)!).
Corollary 3.7. If n is even and (n — sp(n))/(p — 1) is odd, then p divides (n„2). Proof. This follows from Proposition 3.6 and Legendre's formula (3.1). Corollary 3.8. Suppose that n is even.
(a)	If any of the digits in the base p expansion of n/2 is larger than |p/2j, then p
divides („n 2^
(b)	If one of the digits in the base p expansion of n is odd, then p divides (n„2).
Proof. If a digit of n/2 in base p is larger than |p/2J, then when we add n/2 to itself in base p to obtain n there is at least one carry. Similarly, if n has an odd digit in base p, then there is a carry when adding n/2 and n/2 in base p. Hence, by Kummer's Theorem [1 ] with k = n/2, if there is at least one carry when adding n/2 to itself in base p, then p
divides („„2e.	□
Corollary 3.9. Let n be an even positive integer Suppose that there is a prime q such that n/3 < q < n/2 and n — 2q < pa, where pa denotes the largest power of p dividing n. If pLi°g „ / log pi > n/2, then p divides („„2) and therefore n satisfies Condition 1 with p and q.
Proof. The largest value of r such that pr < n < pr+1 is |log n/ log pj. Therefore, in Proposition 3.6, the exponent r is bounded by |_log n/ log pj. Also note that r > a, where a is the largest exponent of p such that pa divides n. If pLlog n/ logpi > n/2, then |n/prJ = 1. Because this is odd, p divides (n„ J by Proposition 3.6.	□
p
304
Ars Math. Contemp. 19 (2020) 189-208
In those cases when the inequalities n - q1 < pa and n - 2q2 < pa both fail for the largest prime power pa dividing n, a possible strategy would be to analyze the inequality n - dqd < pa for bigger values of d, where qd is the largest prime below n/d.
Up to 1,000,000 there are 88 integers that do not satisfy n - 2q2 < pa, where pa is the largest prime power dividing n. The On-Line Encyclopedia of Integer Sequences has published these numbers with the reference A290290 [4]. Among these, there are 25 that do not satisfy the inequality n - 3q3 < pa; there are 7 that do not satisfy the inequality n - 4q4 < pa either; there are 5 for which the inequality n - 5q5 < pa also fails, and there is only one integer for which the inequality n - 6q6 < pa still fails (namely, n = 875160). However, the value of n - dqd need not decrease as d grows, and the number of dangerous intervals that one needs to inspect when n - dqd < pa increases linearly with d. Therefore this strategy is not conclusive, although it often works in practice.
Example 3.10. The largest prime power dividing n = p14# = 13082761331670030 is p = 43. In this case, n - q1 = 89 and n - 2q2 = 268. Thus, Condition 1 fails for p and q1 and it also fails for p and q2. Nevertheless, n - 3q3 = 27 works, as the dangerous interval [q3, n - 2q3] contains one multiple of 43, namely n/3, and (n/3) is divisible by 43. Therefore Condition 1 holds for p = 43 and q3 = 4360920443890001.
Example 3.11. For n = 210, the inequality n - q1 < 7 fails while n - 2q2 < 7 is true. However, is not divisible by 7. Hence we look for greater values of d and find that
n - 5q5 <7 with q5 = 41. Now 42 G [41,46] and 84 G [82, 87], yet S210) and S^0) are both divisible by 7. Hence Condition 1 is satisfied with p = 7 and q5 =41.
Example 3.12. For n = 875160, the inequality n - dqd < 17 is satisfied with d =11 but not with any smaller value of d. There are 6 dangerous intervals of length n - 11q11 = 11. Each of these intervals (except the first) contains one multiple of 17, and in each case the corresponding binomial coefficient (k) happens to be divisible by 17. Therefore Condition 1 is satisfied with p = 17 and q11 = 79559.
4 On the N-variation of Condition 1
Recall from Definition 1.2 that n satisfies the N-variation of Condition 1 if there are N primes p1,... ,pN such that if 1 < k < n - 1 then is divisible by at least one of
p1,... ,Pn .
Theorem 4.1. If an even positive integer n satisfies n - 2q < pa for a prime q with n/3 < q < n/2, where pa is the largest power of p dividing n andp = 2, then n satisfies the 3-variation of Condition 1 with p, q and any prime that divides (n/2).
Proof. According to the statement of part (b) of Theorem 3.5, the only binomial coefficient (k) with 1 < k < n - 1 that might fail to be divisible by p or q is (n/2). Hence it suffices to add an extra prime with this purpose.	□
Proposition 4.2. For a positive integer n, let q1 be the largest prime smaller than n, let pa1 be the largest prime-power divisor of n and let pa2 be the second largest prime-power divisor of n. Ifp^1 pa2 > n - q1, then n satisfies the 3-variation of Condition 1 with p1, p2 and q1 .
S. Casacuberta: On the divisibility of binomial coefficients
305
Proof. By Lucas' Theorem, for any k such that 1 < k < p^1, the binomial coefficient (k) is divisible by pi, and for any k such that n - q1 < k < n/2 the binomial coefficient (k) is divisible by q1. Thus we need to add a prime that divides at least the binomial coefficients (k) with p^1 < k < n - q1 in which k is a multiple of p^1. For this, we pick p2 and therefore we only need to consider those values of k that are, in addition, multiples of p^2. The least k that is a multiple of both prime powers is p^1 p^2. Therefore, if p(L1 p^2 > n - q1, then all values of k lying in the interval p^1 < k < n - q1 are such that (k) is divisible by pi or p2.	□
In the statement of Proposition 4.2, the condition that p^1 p^2 > n - q1 holds by Nagura's bound [ ] if we impose instead that p^1 p^2 > n/6.
For each n, we are interested in the minimum number N of primes such that n satisfies the N-variation of Condition 1. We next discuss upper bounds for N.
Proposition 4.3. For positive integers n and d, suppose that there is a prime q such that n/(d +1) < q < n/d and a prime-power divisor pa of n such that n - dq < pa. Then n satisfies the N-variation of Condition 1 with N = 2 + |_d/2_|.
Proof. By Theorem 2.5, the binomial coefficients (k) are divisible by q except possibly if k lies in a dangerous interval. In the dangerous intervals we only need to consider those integers that are multiples of pa, since otherwise (k) is divisible by p. Since we are assuming that n - dq < pa, we know that in each dangerous interval there is at most one multiple of pa. This means that the worst case is the one in which there is a multiple of pa in every dangerous interval [cq, cq + ft] with 1 < c < |d/2|. Hence we pick one extra prime for each such interval.	□
Corollary 4.4. If 1 < d < 5 and pa > qd + where pa divides n and qd is the largest prime below n/d, and = n - dqd, then n satisfies Condition 1 with p and qd.
Proof. By Lemma 3.2, we may assume that n/(d +1) < qd. If 1 < d < 5, then |_d/2j equals 1 or 2. If |_d/2j = 1, then the assumption that pa > qd + implies that no multiple of pa falls into any dangerous interval until n/2. If |d/2j =2, then we need to check that 2pa > 2qd + in order to ensure that 2pa does not fall into the third dangerous interval. The minimum value of pa such that our assumption pa > qd + holds is qd + + 1. The next multiple of qd + + 1 is 2qd + + 2, which is greater than 2qd + and therefore 2pa does not fall into the third dangerous interval.	□
In order to refine the conclusion of Proposition 4.3, we consider the Diophantine equation
pax - qdy = S,	(4.1)
for 0 < S < = n - dqd, where pa is a prime-power divisor of a given number n and qd is the largest prime below n/d with d > 1. We keep assuming, as above, that qd > n/(d +1). We will also assume that p = qd, which guarantees that (4.1) has infinitely many solutions for each value of S. Specifically, if (x1, y1) is a particular solution for some value of S, then the general solution for this S is
x = X1 + rqd, y = y1 + rpa,
where r is any integer. In the next theorem we denote by N(S) the number of solutions (x, y) of (4.1) with x > 0 and 0 < y < |d/2j for each value of S with 0 < S < ^ Thus N(S) = 0 precisely when (4.1) has no solution (x, y) subject to these conditions.
306
Ars Math. Contemp. 19 (2020) 189-208
Theorem 4.5. For positive integers n and d, suppose that the largest prime qd below n/d satisfies qd > n/(d + 1), and let ¡3d = n — dqd. Let pa be a prime power dividing n with p = qd. Then n satisfies the N-variation of Condition 1 with
3d
N = 2 + ^ N (5),
S=0
where N (5) is the number of solutions (x, y) of pax — qdy = 5 with x > 0 and 0 < y < |_d/2j for each value of 5 with 0 < 5 < 3d.
Proof. The number N(5) counts how many times a multiple of pa falls into a dangerous interval [cqd, cqd + 3d] at a distance 5 from the origin of that interval. Thus we pick an extra prime for each such case, and add two to the sum in order to account for p and qd. □
Example 4.6. The largest prime-power divisor of n = 96135 is p = 29. For d = 4 we find that q4 = 24029 and 34 = 19. Since 24029 = 17 (mod 29), the only solution (x, y) of the Diophantine equation 29x — 24029y = 5 with x > 0 and 0 < y < 2 is (829,1) for 5 = 12. Thus, N(12) = 1 and N = 3 for d = 4. In other words, the only occurrence of a multiple of 29 in a dangerous interval for d =4 is 24041 G [24029, 24048]. This example shows that the bound 2 + |d/2j given in Proposition 4.3 can be lowered.
The number N given by Theorem 4.5 is not a sharp bound. For those multiples pax of pa falling into a dangerous interval [cqd, cqd + 3d], it often happens that the corresponding binomial coefficient (p"x) is divisible by p, as in Example 4.6 or in other examples given in the previous sections. It could also be divisible by qd if d > qd. When d < qd, we have that n satisfies Condition 1 with p and qd if and only if the binomial coefficient (pnx) is divisible by p for every solution (x, y) of (4.1) with x > 0 and 0 < y < [d/2J, since n = dqd + 3d and pax = yqd + 5 with 5 < 3d < qd and y < [d/2j < d, so ( ™x) is not divisible by qd by Lucas' Theorem. Note also, for practical purposes, that (pnx) = (n/£ ) (mod p) .
5 Every number has multiples for which Condition 1 holds
We next prove that every positive integer n has infinitely many multiples for which Condition 1 holds. We are indebted to R. Woodroofe for simplifying and improving our earlier statement of this result, which was based on prime gap conjectures.
It follows from the Prime Number Theorem [7] that, given any real number e > 0, there is a prime between m and m(1 + e) for sufficiently large m. This fact can be used to prove the following:
Theorem 5.1. For every positive integer n and every prime p, the number npk satisfies Condition 1 with p and another prime, for all sufficiently large values of k.
Proof. For any prime p and any k > 0, let m = npk — pk = pk (n — 1). Then
kk
np = m + p = m 1 +
n — 1
Therefore, by the Prime Number Theorem, there is a prime between m and npk for all sufficiently large values of k. Choose the largest prime q with this property. Thus,
npk — pk < q < npk,
S. Casacuberta: On the divisibility of binomial coefficients
307
so npk - q < pk, from which it follows, according to Corollary 2.6, that npk satisfies Condition 1 with p and q.	□
Theorem 5.2. For every positive integer n there is a number M such that ifp is any prime with p > M then np satisfies Condition 1 with p and another prime.
Proof. Given n, let e = 1/(n - 1). Choose m0 such that there is a prime between m and m(1 + e) for all m > m0, and let M = em0. If p is any prime such that p > M, then for
m = p(n — 1) we have
np = m + p = m f1 + —^ = m ( 1+--) = m(1 + e).
V m/	\ n — 1/
Therefore, by our choice of m0, there is a prime between m and np. If q is the largest prime with this property, then np — p < q < np, and consequently np satisfies Condition 1 with p and q.	□
Prime gap conjectures provide information relevant to our problem. For example, if p® denotes the ¿-th prime, then Cramer's conjecture [6] claims that there exist constants M and N such that if p® > N then
pi+1 — pi < M(logpi)2.
Proposition 5.3. Let m be the number of distinct prime factors of n. If Cramer's conjecture is true and n grows sufficiently large keeping m fixed, then n satisfies Condition 1.
Proof. If n has m distinct prime factors, then ^n < pa, where pa is the largest prime-power divisor of n. Let M and N be the constants given by Cramer's conjecture. Pick n0 such that if n > n0 then M(log n)2 < m/n. For every n such that n > n0 and N < p® < n < pi+1 (where p® denotes the i-th prime), we have
n — pi < pi+i — pi < M(logpi)2 < M(logn)2 < /n < pa,
from which it follows that n satisfies Condition 1 with p and p® .	□
We note that the argument used in the proof of Proposition 5.3 yields an alternative proof of the fact that Condition 1 holds for a set of integers of asymptotic density 1 if Cramer's conjecture holds, a result first found in [16, § 5]:
Theorem 5.4 ([16]). If Cramer's conjecture is true, then the set of numbers in the sequence (2.1) has asymptotic density zero.
Proof. Suppose that Cramer's conjecture holds with constants M and N, and denote by w(n) the number of distinct prime divisors of n. Thus n1/w(n) < pa, where pa is the largest prime-power divisor of n. According to [8, § 3.2], for every e > 0 the inequality
w(n) < (1 + e)loglogn	(5.1)
holds for all n except those of a set of asymptotic density zero. Since
n1/log log n
lim ~n-=
n^TO (log n)k
309
Ars Math. Contemp. 19 (2020) 189-208
for all k, there is an n0 such that n1/w(n) > M (log n)2 if n > n0. Now, if n is bigger than n0 and satisfies N < pi < n < pi+1, and moreover n is not in the set of integers for which (5.1) fails, then
n - pi < pi+1 - pi < M (log pi )2 < M (log n)2 < n1/w(n) < p°. Therefore, n satisfies Condition 1 with p and pi.	□
6 Multinomials
We also consider a generalization of Condition 1 to multinomials. We say that a positive integer n satisfies Condition 1 for multinomials of order m if there are primes p and q such that the multinomial coefficient
( n \	n!
\ki,k2,...,km/ ki!k2! ••• km!
is divisible by either p or q whenever k1 + • • • + km = n with 1 < ki < n — 1 for all i.
Proposition 6.1. If n satisfies Condition 1 with two primes p and q, then n satisfies Condition 1 for multinomials of any order m < n with p and q.
Proof. This follows from the equality
/ n \ = / n\/n — kA /n — k1 — kA \k1,k2,...,k^	\ k2 /V k3 y \kW '
and the fact that (kj is divisible by p or q by assumption.	□
Therefore, if Condition 1 is proven for binomial coefficients, then it automatically holds for multinomial coefficients.
ORCID iDs
Silvia Casacubert^ © https://orcid.org/0000-0001-5684-4585 References
[1]	C. Banderier, Fortune's conjecture (Fortunate and unfortunate primes : Nearest primes from a prime factorial), https://lipn.univ-paris13.fr/~banderier/ Computations/prime_factorial.html, last consulted on 11 August 2018.
[2]	J. Bertrand, Memoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme, J. École Roy. Polytechnique 18 (1845), 123-140.
[3]	S. Casacuberta, Sequence A290203 in The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
[4]	S. Casacuberta, Sequence A290290 in The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
[5]	K. S. Davis and W. A. Webb, Lucas' theorem for prime powers, European J. Combin. 11 (1990), 229-233, doi:10.1016/s0195-6698(13)80122-9.
[6]	A. Granville, Harald Cramer and the distribution of prime numbers, Scand. Actuar. J. 1995 (1995), 12-28, doi:10.1080/03461238.1995.10413946.
S. Casacuberta: On the divisibility of binomial coefficients
132
[7]	G. H. Hardy and J. E. Littlewood, Contributions to the theory of the Riemann zeta-function and the theory of the distribution of primes, Acta Math. 41 (1916), 119-196, doi:10.1007/ bf02422942.
[8]	G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Quart. J. Pure Appl. Math 48 (1917), 76-92.
[9]	A. E. Ingham, The Distribution of Prime Numbers, Cambridge Tracts in Mathematics and Mathematical Physics, Cambridge University Press, Cambridge, 1932.
[10]	E. E. Kummer, Uber die Erganzungssatze zu den allgemeinen Reciprocitatsgesetzen, J. Reine Angew. Math 44 (1852), 93-146, doi:10.1515/crll.1852.44.93.
[11]	E. Labos, Sequence A057704 in The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
[12]	A.-M. Legendre, Théorie des nombres, Firmin Didot frères, Paris, 3rd edition, 1830.
[13]	E. Lucas, Theorie des fonctions numeriques simplement periodiques, Amer. J. Math. 1 (1878), 184-196, doi:10.2307/2369308.
[14]	J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), 177-181, doi:10.3792/pja/1195570997.
[15]	L. Schoenfeld, Sharper bounds for the Chebyshev functions 0(x) and ^(x). II, Math. Comp. 30 (1976), 337-360, doi:10.2307/2005976.
[16]	J. Shareshian and R. Woodroofe, Divisibility of binomial coefficients and generation of alternating groups, Pacific J. Math. 292 (2018), 223-238, doi:10.2140/pjm.2018.292.223.
[17]	N. J. A. Sloane (ed.), The On-Line Encyclopedia of Integer Sequences, published electronically
at https://oeis.org.