A survey of Fermat-quotient congruences of Eisenstein’s type
By John Blythe Dobson
The Fermat quotient (r ^{p − 1} − 1)/p with modulus p and base r (which by Fermat’s Little Theorem must be an integer) has been an object of sustained interest since Abel asked in 1828 whether it could be divisible by p. In 1850 Eisenstein showed that its residue mod p could be expressed as a sum of reciprocals of integers relatively prime to the modulus. Interest in Fermat quotients intensified when Wieferich and Mirimanoff demonstrated their connection with the first case of Fermat’s Last Theorem (see the account in Ribenboim [1979]); and even with the proof of FLT by Wiles in 1995, they have continued to figure prominently in studies of binomial congruences and Bernoulli and Euler numbers. It would therefore be desireable to have a clearer idea of the number of known Fermat-quotient congruences, and of whether there are more awaiting discovery.
The present note addresses a piece of this problem by re-examining the congruences of Eisenstein’s type. It expands upon on a brief survey included in an important paper by Dilcher and Skula (1995). We limit ourselves to a discussion of congruences mod p, because the paper of Emma Lehmer (1938) already contains just about everything which can be said about congruences to higher powers of p; therefore all congruences are mod p unless otherwise stated. We do not propose to prove all the relevant formulae from scratch, and develop only as much of the technical apparatus as needed to show how to manipulate a given formula into another equivalent form. We usually employ the brief notation q_{r} to refer to the Fermat quotient (as the form of p will not generally be a concern), but in a few places we use the fuller notation q_{p}(r) when we need to emphasize its function-like behavior. We hope it will be clear that no distinction is intended. Throughout this note, [·] signifies the greatest-integer function.
In the long and extensive literature of Fermat quotients, there is little discernable convention as to how the formulae are to be expressed. We wholeheartedly endorse the treatment in Dilcher and Skula, which is the most coherent and uniform we have seen. If we denote a term in the range from 1 and p − 1 by k, then they arrange their formulae to encompass continuous ranges of k all of the same sign, rather than allowing the series to alternate or choosing only odd or even values, or values belonging only to a particular residue class mod 4 or mod 6. We have never seen a published congruence where this could not be done, and such standardization would surely facilitate comparison with previous results, and discourage the proliferation of exotic variants which have occasionally concealed tautological or vacuous statements. (It is not, however, our intention to disparage any published results, which represent the natural development of diverse methodologies, and which in many cases were presented only as corollaries illustrative of more general theorems.)
It is convenient to classify Fermat-quotient congruences of Eisenstein’s type according to the proportion of the terms in the range from 1 and p − 1 which are comprised in the denominators of the fractions. Despite the fact that these congruences have no value for purposes of actual calculation, refinement of the number of required terms is of considerable theoretical interest. In the case of q_{2}, the formulae involving either all of the terms, or one-half or one-quarter of them, were essentially exhausted by Stern (1887), Glaisher (1901), and Lerch (1905). However, in the last few decades a resurgence of effort in this field has led to the development of an essentially new group of congruences for q_{2}, involving only one-third or one-sixth of the possible terms.
We shall treat three topics: the “original” set of congruences for q_{2} which culminate in the work of Lerch; the “modern” set of congruences for q_{2} which, we feel, receive their best expression in the work of Dilcher and Skula; and finally, q_{3} and its relationship with q_{2}. Preceeding these three topics we shall cover some necessary technical prelimaries, and finally, we shall attempt to address the question of whether any undiscovered congruences remain.
A word of explanation is in order concerning the description of historical results. While we have attempted to be historiographically faithful to the materials, we have for the sake of consistency modernized certain notations such as those relating to summation, and compensated for varying conventions such as when an author writes the Fermat quotient as (r ^{p} − r)/p without factoring r out of the numerator as is now customary. Furthermore, we regard as incidental such questions as whether a coefficient is written in front of a Fermat quotient or its reciprocal is placed on the other side of a congruence; and more importantly, whenever a special case is clearly meant to be inferred from a general formula and such an inference is safely within the grasp of the intended audience, we regard the special case as having been stated and proved. On the other hand, we have been quite particular in indicating such points as whether or not a common factor has been divided out of a sum, or whether the range of a summand is correctly specified, because in our view such matters are not mere niceties but reflect an author’s actual grasp of the material and its relation to an existing body of work.
Preliminaries
In this note, we repeatedly make use of several elementary transposition rules. The first of these we use it as a replacement for the Waring-Wolstenholme theorem [see Hardy and Wright (1960), p. 93], which is frequently invoked in this context, but which, being a congruence mod p^{2}, proves rather more than is needed for our purposes:
Rule A. Because the residues 1 through p − 1 (mod p) are divided by a “center line” lying between (p − 1)/2 and (p + 1)/2, such that terms equidistant from this line are the complements of one another (i.e. they add to p), it follows that any sum symmetrically distributed with respect to the line is congruent to 0 (mod p). Despite its almost truistic basis, this gives rise to a useful supplementary formula for Fermat quotient congruences, in which n is any integer prime to p and greater than 1, and d is an integer greater than 0 but less than (n − 1)/2:
[(n − d)p/n] |
[dp/n] + 1 |
We justify this claim by noting that [(n − d)p/n] + [dp/n] + 1 = [p − dp/n] + [dp/n] + 1 = p + [−dp/n] + [dp/n] + 1 = p − 1 + 1 = p, which proves that the terms in the summand are symmetrically distributed about the “center line.” Most often we use this formula with d = 1:
[(n − 1)p/n] |
[p/n] + 1 |
of which the Waring-Wolstenholme theorem, if considered merely as a congruence mod p, might be regarded as the (degenerate) case in which n > p. If a Fermat-quotient congruence contains a sum which straddles the “center line,” it is possibly not in its simplest form.
Rule B. The second transposition rule shows how an alternating series may be telescoped (mod p), and the signs of the terms brought into accord. This is implicit in the work of Stern but perhaps first clearly articulated (at least in this context) in Glaisher (1901), pp. 21-22. For the sake of simplicity we write this rule so as to cover the whole range of possible terms and to make the odd terms positive, but it can be adapted as necessary:
p − 1 |
1 |
p − 2 |
1 |
k odd |
p − 1 |
2 |
k even |
In the right-hand side, the second member is simply
(p − 1)/2 |
1 |
while the first member is
p − 1 |
2 |
p − k even |
p − 1 |
2 |
k even |
and is thus identical with the second member. Their total is therefore simply
(p − 1)/2 |
1 |
which has only half as many terms as the original formula.
Rule C. The third transposition rule shows how a series expressed as a sum only of odd terms may be condensed into a smaller range of terms which are both odd and even:
n |
1 |
k odd |
2[(n − 1)/2] + 1 |
1 |
k odd |
p − 1 |
2[(p − n + 1)/2] |
k odd |
(p − 1)/2 |
[(p − n + 1)/2] |
(At the second step, we must take some care to ensure that the upper index of summation is an odd integer; and at the third step, we reverse the order of summation.) Conversely, a series expressed as a sum only of even terms may be simplified merely by factoring out the 2 in the denominator of the summand.
Rule D. The fourth transposition rule, which we shall not attempt to define in a formal manner, is that if a congruence is stated as a set of special cases in which the primes p and elements k belong to various residue classes with respect to a modulus (such as 2, 4, or 6), and if p − k falls in fewer distinct residue classes with respect to this modulus than either p or k individually, then the congruence can be simplified (as in rule B above) by replacing k with p − k. This rule is best communicated by illustration, and we shall see it invoked in the ensuing discussions of the work of Sylvester, in particular.
The “original” congruences for q_{2}
These mostly trace their origin to Eisenstein (1850). Connections between Fermat quotients and Wilson quotients were studied by Nielsen (1923). They receive a particularly uniform treatment in Emma Lehmer (1938); see especially p. 358, where they are all generalized to the modulus p^{2}.
Lerch’s work was quoted by Friedmann & Tamarkine (1908) and by Nielsen (1923), but in general the significance of his work seems to have been missed.
The “modern” congruences for q_{2}
The three congruences featured in this section are all drawn from lengthy papers involving deep arguments and diverse subject-matter, and perhaps have not reached a wide audience. In this note, we shall prove — merely by reference to a few of the classical formulae, and with the aid of some elementary series manipulations in the manner of the nineteenth-century writers — the perhaps surprising fact that all three congruences (which require p > 3) are equivalent.
The three results which will be the main object of our interest have r = 2; we present them in the order of their discovery. The earliest was published in Zhi-Hong Sun (1992), p. 230, Corollary 1.3:
[p/3] |
1 |
The second may be readily deduced from the same source, p. 240, Corollary 1.12 (a point to which we will return below), but it is probably first stated explicitly in Dilcher & Skula (1995), p. 389, equation 10.12:
[p/3] |
[p/6] + 1 |
Most recently, Zhi-Wei Sun (2002), p. 138, published the following formula, in our statement of which we have slightly altered the author’s notation for ease of comparison with earlier work:
[(p + 1)/3] |
1 |
k odd |
The congruence (1) may be seen as an elegant sharpening of the famous result of Eisenstein (1850) which inaugurated the development of Fermat-quotient formulae as sums of reciprocals:
p − 1 |
1 |
Clearly, (1) may be subtracted from (4) to give
p − 1 |
[p/3] + 1 |
Next, we may separate the terms into odd and even k, and change only the even k to −k, leading to two distinct sums both over odd k, the second with its sign reversed:
p − 2 |
[p/3] + 1 |
k odd |
[2p/3] |
1 |
k odd |
We then rearrange the terms into two sums, one covering the entire range from 1 to p − 2, the other covering the overlap:
p − 2 |
1 |
k odd |
[2p/3] |
[p/3] + 1 |
k odd |
The first sum, running from 1 to p − 2, is congruent to q_{2} by a formula of Stern (1887), p. 184; Glaisher (1901), p. 27, also proves Stern’s formula, generously attributing (on p. 20) the idea to Sylvester (1861), although in our view Sylvester’s remarks on the subject are hardly more than a hint in this direction. In any case, we therefore have for the second sum:
[2p/3] |
[p/3] + 1 |
k odd |
an expression which involves only 1/6 of the possible terms from 1 to p − 1. Once more setting k = −k to make the terms even, we obtain the same sum occupying the same range, but with the sign reversed:
[2p/3] |
[p/3] + 1 |
k even |
which upon division of the factor ½ out of the summand, becomes (2), a formula which has the advantage that all its terms are contained in a continuous block.
To derive (3) from (1), we begin by rewriting (1) so that the factor ½ is moved into the summand:
[2p/3] |
1 |
k even |
Next, we change k to p − k:
p − 1 |
p − [2p/3] |
p − k even |
Factorising the power of −1, and simplifying the sum, we have:
p − 2 |
[(p + 1)/3] + 1 |
k odd |
We have thus arrived a result comparable to one of Sylvester (1861), p. 230 (with an error), but cast in a better form by Stern (1887), p. 187, which was obtained by a clever but quite elementary method:
p − 2 |
1 |
k odd |
Subtracting (12) twice from (13) gives (3). The reader should be able to verify without too much effort that through processes similar to the above, any of (1) through (3) may be derived from any other, and that they are thus all equivalent.
On q_{3} and its relationship with q_{2}
Sylvester (1861), p. 162, gave a pair of formulae for q_{3}, the second with the wrong sign, which error is missed in the list of corrigenda which Sylvester published that same year, but was silently emended in Sylvester’s Collected Mathematical Papers (1908), 2:230. By then, the correction had already been given by Glaisher, who in his 1901 article, pp. 17-18, had revised them to read:
p − 1 |
1 |
k ≡ 1 (mod 3) |
p − 1 |
1 |
k ≡ 0 (mod 3) |
p − 1 |
1 |
k ≡ 2 (mod 3) |
p − 1 |
1 |
k ≡ 0 (mod 3) |
Again, referring to Rule C, we look for eliminations permitted by the substitution k = p − k, and find that in each case the first terms in the right-hand sides give p − k ≡ 0 (mod 3). Thus both expressions drastically simplify to
p − 1 |
1 |
k ≡ 0 (mod 3) |
p − 1 |
1 |
k ≡ 0 (mod 3) |
p − 1 |
1 |
k ≡ 0 (mod 3) |
and factoring 1/3 out of the summand, we have finally
[p/3] |
1 |
where the summation is taken over all k. This, which we believe should be regarded as the canonical form for this congruence, is precisely that given in Lerch (1905), p. 476, equation no. 16. Lerch was however unaware of Sylvester’s work, and developed his result by a completely different method. (And by yet another completely different method, this congruence was later generalized by Emma Lehmer (1938), p. 358, equation no. 42, to the modulus p^{2}.) Despite the multiple techniques by which this congruence has been derived, it would appear that all the investigations have ultimately been mining the same material, for no other congruence of Eisenstein’s type has ever been obtained for q_{3}.
Adding (1) and (8) and dividing the result by 2 yields the relation
[p/3] |
1 |
k odd |
which has already been given by Zhi-Hong Sun (1992), p. 240, Corollary 1.12, Equation 2, or alternatively,
(p − 1)/2 |
[p/3] + 1 |
if we should prefer to eliminate the condition on k. These are closely related to the same author’s Corollary 1.12, Equation 1, which should have been credited to Emma Lehmer (1938), p. 358, equation no. 44:
[p/6] |
1 |
While clearly (18) might be added to or subtracted from (19) to generate individual expressions (mod p) for q_{3} and q_{2}, respectively, the results are not particularly enlightening, and we shall not pursue such an exercise here. More importantly, the sum of (17) and (19) may be deducted from a formula implicit in Eisenstein, but perhaps first state explicitly by Glaisher (1901), pp. 21-22,
(p − 1)/2 |
1 |
to derive (2) in a slightly different way than previously given. Considered purely as functions of q_{2}, the sums in the first and third sixths in the range from 1 through p − 1 are underdetermined, since we are only able to state their sum (i.e. −4q_{2}) and not their individual values. The situation may be summarized as follows:
first sixth | second sixth | third sixth |
−2q_{2} − 3/2 q_{3} | 2q_{2} | −2q_{2} + 3/2 q_{3} |
Thus, in contrast with the situation with eighths discussed above (in which none can be directly determined solely as functions of q_{2}), the second sixth can be explicitly evaluated. We suspect this is the smallest subset of consecutive terms for which this is true.
Bibliography
Dilcher, Karl & Ladislav Skula. “A New Criterion for the First Case of Fermat’s Last Theorem,” Mathematics of Computation 64 (1995): 363-392.
Eisenstein, [G.] “Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen abhängen und durch gewisse lineare Funktional-Gleichungen definirt werden,” Berichte … der Königlich Preußischen Akademie der Wissenschaften zu Berlin 15 (1850): 36–42. Reprinted in Werke, 2:705–711.
Friedmann, A & J. Tamarkine, “Quelques formules concernant la théorie de la fonction [x] et den nombres de Bernoulli,” Journal für die reine und angewandte Mathematik 135 (1908): 146-156.
Glaisher, J.W.L. “On the Residues of r ^{p−1} to Modulus p^{2}, p^{3}, etc.,” Quarterly Journal of Pure and Applied Mathematics 32 (1901): 1-27.
Lehmer, Emma. “On Congruences involving Bernoulli Numbers and the Quotients of Fermat and Wilson,” Annals of Mathematics 39 (1938): 350-360.
Lerch, M. “Zur Theorie des Fermatschen Quotienten…,” Mathematische Annalen 60 (1905): 471-490. Available online at http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235181684_0060&DMDID=dmdlog56.
Lerch, M. “Sur les théorèmes de Sylvester concernant le quotient de Fermat,” Comptes Rendus de l’Académie des Sciences 142 (1906): 35-38. This is a summary of Lerch (1905).
Nielsen, Niels. Traité Élémentaire des Nombres de Bernoulli. Paris, 1923.
Ribenboim, Paulo. 13 Lectures on Fermat’s Last Theorem. New York, &c.: Springer-Verlag, 1979.
Stern, M. “Einige Bemerkungen über die Congruenz (r ^{p} − r)/p ≡ a (mod p),” Journal für die reine und angewandte Mathematik 100 (1887): 182-188. Available online at http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN243919689_0100&DMDID=dmdlog18.
Sun, Zhi-Hong. “[The] Combinatorial Sum and its Applications in Number Theory, I” (in Chinese), Nanjing University Journal — Mathematical Biquarterly 9 (1992): 227-240. A very full summary in English is available on the author’s website, at http://www.hytc.cn/xsjl/szh/coms1.pdf..
Sun, Zhi-Wei. “On the Sum and Related Congruences,” Israel Journal of Mathematics 128 (2002): 135-56.
Sylvester, J.J. “Sur une propriété des Nombres Premiers qui se ratache au Théorème de Fermat,” Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences 52 (1861): 161–163, 212–214 (correction), 307–308 (addendum), 817 (further correction). Reprinted in Collected Mathematical Papers, 2:229–31 (with the briefer corrections incorporated, and also some silent editorial corrections), 232–233, 234–35, 241.
Published 7 October 2007