SOME DIVISIBILITY PROPERTIES OF BINOMIAL COEFFICIENTS Daniel Yaqubi1 and Madjid Mirzavaziri2 7 1 0 2 1,2Department of Pure Mathematics, Ferdowsi University of Mashhad n P. O. Box 1159, Mashhad 91775, Iran. a J Email1: daniel [email protected] 2 2 Email2: [email protected] ] O C . h Abstract. In this paper, we aimto givefull proofs or partialanswersfor the following t a three conjectures of V. J. W. Guo and C. Krattenthaler: (1) Let a > b be positive m integers,α,β be anyintegersandpbe aprime satisfyinggcd(p,a)=1. Thenthere exist [ infinitely many positive integers n for which an+α ≡ r (mod p) for all integers r; (2) 1 bn+β v Foranyoddprimep,therearenopositiveinteg(cid:0)ersa(cid:1)>bsuchthat abnn ≡0 (mod pn−1) 7 for all n ≥ 1; (3) For any positive integer m, there exist positive integers a and b such 1 (cid:0) (cid:1) 2 that am>b and amn ≡0 (mod an−1)for all n≥1. Moreover,we show that for any bn 6 positiveintegerm,therearepositiveintegersaandbsuchthat amn ≡0 (mod an−a) 0 (cid:0) (cid:1) bn . for all n>1. 1 (cid:0) (cid:1) 0 7 1 1. introduction : v i Binomial coefficients constitute an important class of numbers that arise naturally in X r mathematics, namely as coefficients in the expansion of the polynomial (x+y)n. Accord- a ingly, they appear in various mathematical areas. An elementary property of binomial coefficients is that n is divisible by a prime p for all 1 < m < n if and only if n is a m power of p. A much more technical result is due to Lucas, which asserts that (cid:0) (cid:1) n n n n 0 1 k ≡ ··· (mod p), m m m m (cid:18) (cid:19) (cid:18) 0(cid:19)(cid:18) 1(cid:19) (cid:18) k(cid:19) in which n = n +n p+···+n pk and m = m +m p+···+m pk the p-adic expansions 0 1 k 0 1 k of the non-negative integers n and m, respectively. We note that 0 ≤ m ,n < p, for all i i 2010 Mathematics Subject Classification. Primary 11B65; Secondary 05A10. Key words and phrases. Binomial coefficients, p-adic valuation, Lucas’ theorem, Euler’s totient theo- rem, Bernoulli numbers. 1 2 DANIEL YAQUBIAND MADJID MIRZAVAZIRI i = 0,...,k. In 1819, Babbage [1] revealed the following congruences for all odd prime p: 2p−1 ≡ 1 (mod p2). p−1 (cid:18) (cid:19) In1862, Wolstenholme [7]strengthened theidentity ofBabbagebyshowing thatthesame congruence holds modulo p3 for all prime p ≥ 5. This identity was further generalized by Ljunggren in 1952 to np ≡ n (mod p3) and even more to np / n ≡ 1 (mod pq) by mp m mp m Jacobsthal for all positive integers n > m and primes p ≥ 5, in which pq is any power (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) of p dividing p3mn(n−m). Note that the number q can be replaced by a large number if p divides B , the (p − 3)’th Bernoulli number. Arithmetic properties of binomial p−1 coefficients are studied extensively in the literature and we may refer the interested reader to [?] for an account of Wolstenholme’s theorem. Recently, Guo and Krattenthaler [2] studied a similar problem and proved the following conjecture of Sun [5]. Theorem 1.1. Let a and b be positive integers. If bn+1 divides an+bn for all sufficiently an large positive integers n, then each prime factor of a divides b. In other words, if a has (cid:0) (cid:1) a prime factor not dividing b, then there are infinitely many positive integers n for which bn+1 does not divide an+bn . an They also stated sev(cid:0)eral co(cid:1)njectures among which are the following, which we aim to give full proofs for two conjectures and a partial answer for one of them. Conjecture 1.2 ([2, Conjecture 7.1]). Let a > b be positive integers, α,β be any integers and p be a prime satisfying gcd(p,a) = 1. Then there exist infinitely many positive integers n for which an+α ≡ r (mod p) bn+β (cid:18) (cid:19) for all integers r. Conjecture 1.3 ([2, Conjecture 7.2]). Foranyoddprimep, therearenopositive integers a > b such that an ≡ 0 (mod pn−1) bn (cid:18) (cid:19) for all n ≥ 1. Conjecture 1.4 ([2, Conjecture 7.3]). For any positive integer m, there exist positive integers a and b such that am > b and amn ≡ 0 (mod an−1) bn (cid:18) (cid:19) SOME DIVISIBILITY PROPERTIES OF BINOMIAL COEFFICIENTS 3 for all n ≥ 1. Moreover, we show that for any positive integer m, there are positive integers a and b such that amn ≡ 0 (mod an−a) for all n > 1. bn (cid:0) (cid:1) 2. Conjecture 1.3 OurfirstresultisamorepreciseversionofConjecture1.3inthiscasethata 6≡ 0(mod p) and we obtain some divisibility property of binomial coefficients. Theorem 2.1. For any odd prime p, there are no positive integers a > b with a 6≡ 0 (mod p) such that an ≡ 0 (mod pn−1), bn (cid:18) (cid:19) for all n > 1. Proof. There are two cases. Case I. a 6≡ 0 (mod p) and b 6≡ 0 (mod p). There is an 1 6 s 6 p−1 such that sb ≡ 1 (mod p). We may write sa = pQ+r, 1 6 r 6 p−1 ′ sb = pQ +1. Choose t such that st ≡ −1 (mod p). Thus there is a k with st = kp−1. We claim that aK (pn+t)(p+s) = pK −1 | , bK (cid:18) (cid:19) where K = pn+ns+t+k. By Dirichlet’s theorem, there are infinitely many primes of the form pn+t. If pn+t is prime, Lucas’ theorem implies that aK a(pn+ns+t+k) = bK b(pn+ns+t+k) (cid:18) (cid:19) (cid:18) (cid:19) a(pn+t)+a(ns+k) = b(pn+t)+b(ns+k) (cid:18) (cid:19) a(pn+t)+Q(pn+t)+rn+ak −Qt = b(pn+t)+Q′(pn+t)+n+bk −Q′t (cid:18) (cid:19) a+Q rn+ak −Qt ≡ (mod pn+t), b+Q′ n+bk −Q′t (cid:18) (cid:19)(cid:18) (cid:19) since for sufficiently large n we have rn+ak −Qt,n+bk −Q′t < pn+t. 4 DANIEL YAQUBIAND MADJID MIRZAVAZIRI Now we have ′ ′ ′ s(n+bk −Qt) = sn+(pQ +1)k−Q(pk −1) ′ = sn+k +Q 6 srn+rk+Q 6 srn+(pQ+r)k −Q(pk −1) = s(rn+ak −Qt). Whence rn+ak−Qt 6= 0. n+bk−Q′t Case II. a 6≡ 0 (mod p) and b ≡ 0 (mod p). (cid:0) (cid:1) We should have aK a+Q rn+ak −Qt 0 ≡ ≡ (mod pn+t), bK b+Q′ bk −Q′t (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) where K = pn+t+k. That is impossible for sufficiently large n. (cid:3) In the next theorem we aim at considering the case a = cp and b = pk + r, where 1 6 r 6 p−1 and we give a partial answer for Conjecture 1.3 in this case. We know that for each prime number p and ε > 0 there is a real number M (ε) p such that for each x > M (ε) there is a prime number q in the interval (x,(1 + ε)x) p with q ≡ −1 (mod p) [3]. Moreover, there is a real number M′(ε) such that for each p x > M′(ε) there are at least two prime numbers q,q′ in the interval (x,(1 + ε)x) with p q,q′ ≡ −1 (mod p). In the following we may assume b < c(p−r), since if b > c(p−r) then pcn = pcn , bn b′n where b′ = pc−b. We have b′ = pk′+r′, where k′ = c−k−1,r′ = p−r and b′ < c(p−r′). (cid:0) (cid:1) (cid:0) (cid:1) Theorem 2.2. Let p be an odd prime, 1 6 r 6 p−1 and γ = p2r+p2+r2−pr. p2(p+1) i. If pk + r 6 cp(1 − γ) then there are no positive integers c > M ( (p−r)2 ) and k p pr(p+1) such that pcn ≡ 0 (mod pn−1). (pk +r)n (cid:18) (cid:19) for all n > 1. ii. If cp(1−γ) < pk +r < c(p−r) and r 6 p−3 then there are no positive integers 2 k > 2M′(p−(2r+1)) and c such that p p+1 pcn ≡ 0 (mod pn−1). (pk +r)n (cid:18) (cid:19) for all n > 1. SOME DIVISIBILITY PROPERTIES OF BINOMIAL COEFFICIENTS 5 Proof. i. Put b = pk +r. We have −b > (γ −1)p. Thus c p(c−k) −1 p(c−k)−r p b p γp p (p−r)2 r = = − > + − = 1+ > 1. c rc r rc r r r pr(p+1) Now since c > M ( (p−r)2 ), there is a prime number pn−1 with p pr(p+1) p(c−k) c < pn−1 < −1. r This implies the result, since k 6 rn+k 6 c < pn−1 and Lucas’ theorem implies pcn c(pn−1)+c c c = ≡ (mod pn−1). (pk +r)n k(pn−1)+rn+k k rn+k (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) ii. For α = p+1 we have 2(p−r) k 2(p−r) p−(2r +1) = = 1+ > 1 αk p+1 p+1 and since αk > M′(p−(2r+1)), there are two prime numbers pm − 1,pn − 1 with αk < p p+1 pm−1 < pn−1 < k. We have b−r c(p−r)−r r(c+1) k = < = c− < c. p p p Furthermore, k +1 rk +b rk +c(p−r) rc+c(p−r) rn+k < r · +k = < < = c. p p p p Moreover, c b kp+r p+1 < = 6 , k k(1−γ)p kp· (p2+r)(p−r) p−r p2(p+1) where the last inequality is true since k > p. We can therefore deduce that p+1 p−r pn−1 < k < c < 2· k = 2αk < 2(pm−1). 2 We have c+1 6 2(pm−1) < 2(pn−1). Write c = (pn−1)+R and rn+k = (pn−1)+R′. We know that pn−1 > R > R′. Now Lucas’ theorem implies pcn c(pn−1)+(pn−1)+R c+1 R = ≡ (mod pn−1). (pk +r)n k(pn−1)+(pn−1)+R′ k +1 R′ (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) The latter is not congruent to 0, since c+1 k +1 c−k ⌊ ⌋−⌊ ⌋−⌊ ⌋ 6 1−1−0 = 0. pn−1 pn−1 pn−1 (cid:3) 6 DANIEL YAQUBIAND MADJID MIRZAVAZIRI Lemma 2.3. Let p be an odd prime, 1 6 r 6 p−2,j = ⌊ p ⌋ and α = p . Then p−r (p−r)(j+1) there is an 0 < ε(p,r) < 1 such that r p+ε(p,r) p−r α < < . (p−r)(j +1) j −1+ r p Proof. A simple verification shows that r p−r α < j −1+ r p if and only if p−r ∤ p or equivalently r 6= p−1. This implies the existence of ε(p,r). (cid:3) On the other hand, let c = j(pn−1)+R,0 6 R 6 pn−2 and rn+k = (pn−1)+R′,0 6 R′ 6 pn−2 and suppose pn−1 = θk, where α < θ < β. Then by Lemma 2.3, ′ R +jθk = k −(pn−1)+rn+jθk θk +1 = k −θk +r · +jθk p r r = k(1+(−1+ +j)θ)+ p p r r 6 k(1+(−1+ +j)β)+ p p r r = k(1+(j −1+ )β)+ p p r r < k(1+ )+ p−r p p r < k + p−r p−r < c. Hence ′ R = c−j(pn−1) = c−jθk > R. This shows that c rn+k c−(rn+k) R−R′ ⌊ ⌋−⌊ ⌋−⌊ ⌋ = j −1−(j −1+⌊ ⌋) = 0. pn−1 pn−1 pn−1 pn−1 3. Conjecture 1.4 In this section, using only properties of the p-adic valuation we give an inductive proof of Conjecture 7.3 of [2]. For n ∈ N and a prime p, the p-adic valuation of n, denoted by ν (n) is the highest power of p that divides n. The expansion of n ∈ N in base p is p SOME DIVISIBILITY PROPERTIES OF BINOMIAL COEFFICIENTS 7 written as n = n +n p+...+n pk with integers 0 6 n 6 p−1 and n 6= 0. Legendre’s 0 1 k i k classical formula for the factorials ν (n!) = ∞ ⌊n⌋ appears in elementary textbooks. p i=1 pi P Theorem 3.1. For any positive integer m, there are positive integers a and b such that am > b and amn ≡ 0 (mod an−1) bn (cid:18) (cid:19) for all n > 1. Proof. Let p = 2 < p = 3 < p = 5 < ... be the sequence of prime numbers. Choose t 1 2 3 such that p > 3m and put t a = 6p ...p , 3 t b = 4p ...p . 3 t Let n be a positive integer and qα | an−1 for some prime number q. We aim at showing that qα | amn . This of course proves that an−1 | amn . bn bn Write bn in base q in the form N r qj, where N = α −1 or α since bn > qα−1. At (cid:0) (cid:1) j=0 j (cid:0) (cid:1) first we show that m < r . We have 0 P ∗ ∗ ∗ r ≡ bn = 4p ...p n ≡ 2·3 ·6p ...p n = 2·3 an ≡ 2·3 (mod q), 0 3 t 3 t where 3∗ is the inverse of 3 mod q. We know that q+1 if 3 | q+1 3∗ = 3 ( 2q+1 if 3 | q+2 3 Note that 3∗ exists since q 6= 3. We thus have 2· q+1 > q if 3 | q +1 r = 2·3∗ = 3 3 0 ( 2· 2q+1 −q = q+2 > q if 3 | q +2 3 3 3 We have gcd(q,p p ...p ) = 1. Hence q > p > 3m. This shows that m < r . We 1 2 t t 0 therefore have ⌊bn−m⌋ = ⌊ Nj=0rjqj −m⌋ = ⌊ N r qj−i + ij−=11rjqj +r0 −m⌋ = N r qj−i = ⌊bn⌋. j j qi qi qi qi P j=i P j=i X X 8 DANIEL YAQUBIAND MADJID MIRZAVAZIRI Now let an−1 = kqα, where gcd(k,q) = 1. We evaluate the q-adic valuation v ( amn ). q bn If N = α then (cid:0) (cid:1) α amn amn bn (am−b)n v > ⌊ ⌋−⌊ ⌋−⌊ ⌋ q bn qi qi qi (cid:18) (cid:19) i=1 (cid:0) (cid:1) X(cid:0) (cid:1) α bn (am−b)n > mkqα−i −⌊ ⌋−⌊ ⌋ qi qi i=1 X(cid:0) (cid:1) α bn mkqα +m−bn = mkqα−i −⌊ ⌋−⌊ ⌋ qi qi i=1 X(cid:0) (cid:1) α bn m−bn = mkqα−i −⌊ ⌋−mkqα−i −⌊ ⌋ qi qi i=1 X(cid:0) (cid:1) α bn bn−m = −⌊ ⌋−⌊− ⌋ qi qi i=1 X(cid:0) (cid:1) α bn bn−m = −⌊ ⌋+⌊ ⌋+1 qi qi i=1 X(cid:0) (cid:1) α = 1 = α, i=1 X since bn−m is not an integer. qi On the other hand, if N = α−1 then α−1 amn amn bn (am−b)n v = mk + ⌊ ⌋−⌊ ⌋−⌊ ⌋ q bn qi qi qi (cid:18) (cid:19) i=1 (cid:0) (cid:1) X(cid:0) (cid:1) > mk +α−1 > α. Thus qα | amn . bn (cid:3) (cid:0) (cid:1) Theorem 3.2. For any positive integer m, there are positive integers a and b such that amn ≡ 0 (mod an−a) bn (cid:18) (cid:19) for all n > 1. Proof. Let p = 2 < p = 3 < p = 5 < ... be the sequence of prime numbers. For a 1 2 3 positive integer t put b = ap ...p . 3 t SOME DIVISIBILITY PROPERTIES OF BINOMIAL COEFFICIENTS 9 Let n be a positive integer and qα | an − a for some prime number q. It is sufficient qα | amn , this concludes the proof. Let b = r +r q+...+r qα is the q-adic expansions bn 0 1 α of b where 0 ≤ r ≤ q −1. We have gcd(q,p p ...p ) = 1 and r ≡ b (mod q). Now, let (cid:0) (cid:1) i 1 2 t 0 an = a+kqα where gcd(k,q) = 1. We evaluate the q-adic valuation v ( amn ). We have q bn amn (amn)! (cid:0) (cid:1) v = v q q bn (bn)!(amn−bn)! (cid:18) (cid:19) (cid:0) (cid:1) α(cid:0) (cid:1) amn bn anm−bn = ⌊ ⌋−⌊ ⌋−⌊ ⌋ qi qi qi i=1 X(cid:0) (cid:1) α mkqα +ma anp p ...p anm−anp p ...p 1 2 t 1 2 t = ⌊ ⌋−⌊ ⌋−⌊ ⌋ qi qi qi i=1 X(cid:0) (cid:1) α am b am−b = ⌊ ⌋−⌊ ⌋−⌊ ⌋ qi qi qi i=1 X(cid:0) (cid:1) So, it is sufficient to show for any m ∈ Z+ the inequality am b am−b ⌊ ⌋−⌊ ⌋−⌊ ⌋ > 0 (3.1) qi qi qi Let ma = s+r and b = s′+r′ where s,s′ ∈ Z+ and0 6 r,r′ 6 1, then⌊am⌋−⌊b ⌋ = s+s′ qα qα qi qi and ⌊am−b⌋ = s+s′ or s+s′ −1. Therefore 3.1 holds and this concludes the proof. (cid:3) qi 4. Conjecture 1.2 Maxim Vsemirnov [6] proved that the conjecture 1.2 is not true for p = 5. He also proved the following theorem: Theorem 4.1. Let p = 5,a = 4,b = 2. If (α,β) ∈ {(0,0),(1,0),(1,1)} then 4n+α ≡ 0,1 or 4 (mod 5); 2n+β (cid:18) (cid:19) If (α,β) ∈ {(2,1),(3,1),(3,2)} then 4n+α ≡ 0,2 or 3 (mod 5); 2n+β (cid:18) (cid:19) In the following, we give a proof for a special case of Conjecture 1.2 We know that if gcd(x,y) = 1 then there is an integer 1 6 x′ 6 y−1 such that y | xx′−1. We denote this x′ by Inv (x). Moreover, for an integer x we denote the p-adic valuation of x by v (x). y p 10 DANIEL YAQUBIAND MADJID MIRZAVAZIRI Theorem 4.2. Let a and b be positive integers with a > b, let α and β be integers and let d = gcd(a,b),c = a,e = gcd(p−1,a). Furthermore, let p be a prime such that p > a+2b. d Then i. if e < c or v (a) 6 v (p−1) then for each r = 0,1,...,p−1, there are infinitely 2 2 many positive integers n such that an+α ≡ r (mod p); bn+β (cid:18) (cid:19) ii. if e > c and v (a) > v (p−1) then for each 2 2 e+2−p−α c+1−α r ∈/ {(2µ−1)e+p+α−2+r′ : 0 6 r′ 6 e−c,⌈ ⌉ 6 µ 6 ⌈ ⌉}, 2e 2e there are infinitely many positive integers n such that an+α ≡ r (mod p). bn+β (cid:18) (cid:19) Proof. By Euler’s totient theorem, we have pϕ(a) ≡ 1 (mod a), since gcd(p,a) = 1. For an arbitrary positive integer N, put u = Nϕ(a). Thus pui ≡ 1 (mod a), i ∈ N. Inparticular, thereisanmsuchthatpu−1 = am. Thusm = −Inv (a). Putt = (p−1)−r. p Write c−t−α = µe+ρ, where 0 6 ρ 6 e−1. Note that e | c−t−α−ρ. Suppose 0 if ρ 6 c−2 ε = ( 1 otherwise If e < c then put c−t−α−ρ p(p−1) K = · pInva( ) e e e +(c−t−α−ρ(cid:0))amInv (a+1)−(cid:1)(β −1)a2mInv (b(a+1))+Lpa, p p where L is sufficiently large so that K > 1. Note that ε = 0 in this case, since ρ 6 e−1 6 c−2. If e > c and v (a) 6 v (p−1) then put 2 2 c−t−α−ρ p(p−1)(1+ε) K = · pInva( ) e e e +(c−t−α−ρ(cid:0))amInv (a+1)−(β −1(cid:1))a2mInv (b(a+1))+Lpa, p p where L is sufficiently large so that K > 1. Note that Inva(1+ε) exists, since a is odd e e in this case.