ANALOGUES OF THE BINOMIAL COEFFICIENT THEOREMS OF GAUSS AND JACOBI by Abdullah Al-Shaghay Submitted in partial fulfillment of the requirements for the degree of Master of Science at Dalhousie University Halifax, Nova Scotia March 2014 (cid:2)c Copyright by Abdullah Al-Shaghay, 2014 Table of Contents List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Abbreviations and Symbols Used . . . . . . . . . . . . . . . . . . vi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 The Theorems of Gauss and Jacobi . . . . . . . . . . . . . . . . . . . 1 1.2 The Theorem of Hudson and Williams . . . . . . . . . . . . . . . . . 5 1.3 Morley’s Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Uses and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Chapter 2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Gauss Factorials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Morita’s p-adic Gamma Function . . . . . . . . . . . . . . . . . . . . 10 2.3 Gauss and Jacobi Sums . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 The Gross-Koblitz Formula . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Evaluations of Certain Jacobi Sums . . . . . . . . . . . . . . . . . . . 18 2.6 Some Special Number Sequences . . . . . . . . . . . . . . . . . . . . . 19 2.7 Congruences for Certain Finite Sums . . . . . . . . . . . . . . . . . . 21 2.8 Primes and Sums of Squares . . . . . . . . . . . . . . . . . . . . . . . 26 Chapter 3 Congruences for Binomial Coefficients Modulo p3 . . . 31 3.1 The p ≡ 1 (mod 6) case . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 The p ≡ 1 (mod 4) case . . . . . . . . . . . . . . . . . . . . . . . . . 55 ii 3.3 The p ≡ 1 (mod 8) case . . . . . . . . . . . . . . . . . . . . . . . . . 61 Chapter 4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.1 p-adic Expansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2 Further Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4 Appendix: List of Congruences modulo p3 . . . . . . . . . . . . . . . 69 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 iii List of Tables Table 2.1 Table 3.2.1 in [1].. . . . . . . . . . . . . . . . . . . . . . . . . . 18 Table 2.2 Table 3.1.2 in [1].. . . . . . . . . . . . . . . . . . . . . . . . . . 19 Table 2.3 B ,E , and B (x) for 0 ≤ n ≤ 8. . . . . . . . . . . . . . . . . . 20 n n n Table 4.1 The case p ≡ 1 (mod 4). . . . . . . . . . . . . . . . . . . . . . 69 Table 4.2 The case p ≡ 1 (mod 6). . . . . . . . . . . . . . . . . . . . . . 70 iv Abstract Two of the more well known congruences for binomial coefficients modulo p, due to Gauss and Jacobi, are related to the representation of an odd prime (or an integer multiple of the odd prime) p as a sum of two squares (or an integer linear combination of two squares). These two congruences, along with many others, have been extended to analogues modulo p2 and are well documented in [1]. More recently, J. Cosgrave and K. Dilcher, in [7] and [9], have extended the congruences of Gauss and Jacobi and a related one due to Hudson and Williams, to analogues modulo p3. In this thesis we discuss their methods as well as the potential of applying them to similar congruences found in [1]. v List of Abbreviations and Symbols Used In what follows, and throughout this thesis, n and r always denote a positive integer, p a prime, and q a power of a prime. Notation Description a ≡ b (mod n) a is congruent to b modulo n; that is, b−a = kn for some integer k. a (cid:5)≡ b (mod n) a is not congruent to b modulo n; that is, b−a (cid:5)= kn for any integer k. gcd(a,b) Greatest common divisor of a and b. (cid:2) (cid:3) n Binomial coefficient defined by n! . k (n−k)!k! q (m) Fermat quotient defined by mp−1−1. p p E The nth Euler number. n (cid:2) (cid:3) C The nth Catalan number defined by 1 2n . n n+1 n B (x) The nth Bernoulli polynomial. n B The nth Bernoulli number. n N ! Gauss factorial of N modulo n. n Q Field of rational numbers. Z Ring of integers. Q Field of p-adic numbers. p Z Ring of p-adic integers in Q . p p Z∗ Group of units in Z . p p F Finite field with q elements. q F∗ Group of units in F . q q G (β,χ) Gauss sum for the element β and the character χ. r J (χ,ψ) Jacobi sum for the characters χ and ψ. r Q(α ,...,α ) The smallest subfield of C containing Q and α ,...,α . 1 n 1 n Z[α ,...,α ] The smallest subring of C containing Z and α ,...,α . (cid:4) (cid:5)1 n 1 n a Legendre symbol of a and p defined for integers a and odd primes p for p which p (cid:2) a to be 1 if x2 ≡ a (mod p) for some x and -1 otherwise. vi Notation Description a | b a divides b; that is, b = ak for some integer k. a (cid:2) b a does not divide b, that is, b (cid:5)= ak for any integer k. ind a Index of a base g modulo p defined to be the least nonnegative integer g k such that gk ≡ a (mod p). p A prime ideal in the given ring of integers that divides the prime p. m ≡ n (mod a) m is congruent to n modulo the ideal a; that is, the element m+(−n) belongs to the ideal a. vii Acknowledgements I would like to especially thank my supervisor, Dr. Karl Dilcher, for everything he has done for me. He is a wonderful teacher, supervisor, and mentor. This thesis would not have been possible without his assistance, patience, and understanding. I would like to thank Dr. Rob Noble and Dr. Keith Johnson for taking the time to read and comment on my thesis. I really value and respect both of your opinions; all of your help is greatly appreciated. Iwouldliketothankmyfamilyandfriendsfortheircontinued support throughout my education. They have always been a great source of encouragement and advice. Finally, I would like to thank the Department of Mathematics and Statistics at Dalhousie University for all of their support. The faculty, administrative staff, and other students have made my experience very enjoyable. viii Chapter 1 Introduction Many mathematicians were interested in the problem of determining the value of bi- nomial coefficients modulo an odd prime p; among them were C. Gauss, C. Jacobi, E. Lehmer, A.Whiteman, L. von Schrutlea, R. Hudson, and K. Williams. In the late 1980s, a number of authors began considering the problem of determining the value of binomial coefficients modulo p2 rather than modulo p [1, Chapter 9]. In this thesis, we will be concerned with determining the value of binomial coefficients modulo p3. 1.1 The Theorems of Gauss and Jacobi One of the earliest and better known congruences for binomial coefficients, due to Gauss (1828), is related to the representation of an odd prime p (congruent to 1 mod- ulo 4) as a sum of two squares. Let p ≡ 1 (mod 4) be prime. It is well known that such primes p admit a repre- sentation as a sum of two integer squares. But if we consider such a representation p = a2 + b2 for integers a and b modulo 4, and use the fact that the only squares modulo 4 are 0 and 1, we can conclude that exactly one of a2, b2 is congruent to 1 modulo 4 (and the other is congruent to 0 modulo 4). Without loss of generality, we may then suppose that a2 ≡ 1 (mod 4) so that a ≡ ±1 (mod 4). Finally, by switch- ing the sign of a, if necessary, we can assume that a ≡ 1 (mod 4). The following notation that will be used in several of the following results therefore makes sense. 1 2 p = a2 +b2 ≡ 1 (mod 4) where a ≡ 1 (mod 4) (1.1) Theorem 1.1. Let p,a,b satisfy (1.1). Then (cid:6) (cid:7) p−1 2 ≡ 2a (mod p). p−1 4 This congruence was discovered by Gauss as a result of his work on quartic and biquadratic reciprocity (see, e.g., [25, Section 6.2]). Beukers, in [2], conjectured the following modulo p2 extension of this congruence which was proven by Chowla, Dwork, and Evans in 1986 [4]. Theorem 1.2. Let p,a,b satisfy (1.1). Then (cid:6) (cid:7) (cid:6) (cid:7) (cid:4) (cid:5) p−1 1 p 2 ≡ 1+ pq (2) 2a− (mod p2), p−1 2 p 2a 4 where q (m) denotes the Fermat quotient, defined for integers m and odd primes p (cid:2) m p by mp−1 −1 q (m) := . p p More recently, Cosgrave and Dilcher [7] (2010) have extended this congruence to the following analogue modulo p3. Theorem 1.3. Let p,a,b satisfy (1.1). Then (cid:6) (cid:7) (cid:6) (cid:7)(cid:6) (cid:7) p−1 p p2 1 1 (cid:2) (cid:3) 2 ≡ 2a− − 1+ pq (2)+ p2 2E −q (2)2 (mod p3). p−1 2a 8a3 2 p 8 p−3 p 4 Here E denotes the (p −3)rd Euler number, where the Euler numbers E ,n ≥ 0 p−3 n