Fermat quotients  q_p(a)  that are divisible by  p

Wilfrid Keller and Jörg Richstein

Let  p  be an odd prime and  a  an integer not divisible by  p.  Then the integer  q_p(a) = (a ^p-1 - 1) / p  is called the Fermat quotient of  p  with base  a.  The number  q_p(a)  may again be divisible by  p.  This is equivalent to saying that the congruence  a ^p-1 = 1 (mod p²)  is satisfied for the pair  (a, p).  Such pairs are of interest in relation to several number theoretical questions. Prime bases  a  are particularly relevant. One usual approach for listing solutions of the mentioned congruence is to fix  a  and give the corresponding values of  p  that yield a solution.

Below a complete list of solutions  (a, p)  is given for odd prime bases  a < 1000  and primes  p < 10¹¹.  For the particular bases  a = 3  and  a = 5  the larger interval  p < 10¹³  is covered. The bases  a = 29, 47, 61, 113, 139, 311, 347, 983  remained without a known solution  p,  while for  a = 929  the first solution occurred at  p = 62199604679.  Generally, the two largest  p  are in the pairs  (5, 188748146801)  and  (881, 94626144313),  and  a = 937  has the highest number of known solutions (eight values of  p).

The appended table is the result of extensive computations carried out by the authors of this page. As far as the considered prime bases  a < 1000  are concerned, earlier tabulations were thoroughly confirmed. Starting with the work of Riesel and of Kloss, successive extensions are found in the following references, which are listed chronologically.

• H. Riesel, Note on the congruence a ^p-1 = 1 (mod p²), Math. Comp. 18 (1964), 149-150. MR 28:1156.
• K. E. Kloss, Some number-theoretic calculations, J. Res. Nat. Bur. Standards 69B (1965 ), 335-336. MR 32:7473.
• J. Brillhart, J. Tonascia and P. Weinberger, On the Fermat quotient, Computers in Number Theory (A. O. L. Atkin and B. J. Birch, eds.), Academic Press, London and New York, 1971, 213-222. MR 47:3288.
• W. Keller, New prime solutions p of a ^p-1 = 1 (mod p²), Abstracts Amer. Math. Soc. 9 (1988), 503.
• M. Aaltonen and K. Inkeri, Catalan's equation x ^p - y ^q and related congruences, Math. Comp. 56 (1991), 359-370. MR 91g:11025.
• P. L. Montgomery, New prime solutions of a ^p-1 = 1 (mod p²), Math. Comp. 61 (1993), 361-363. MR 94d:11003.
• W. Keller, Prime solutions p of a ^p-1 = 1 (mod p²) for prime bases a, Abstracts Amer. Math. Soc. 19 (1998), 394.
• W. Keller and J. Richstein, Prime solutions p of a ^p-1 = 1 (mod p²) for prime bases a, II, Abstracts Amer. Math. Soc. 20 (1999), 228.

Further properties of solutions  (a, p)  have also been examined. First, we looked to see whether a solution might also satisfy  a ^p-1 = 1 (mod p^r)  for  r > 2.  In our list there are in fact 32 pairs  (a, p)  which satisfy the congruence for  r = 3.  But they all have very small values of  p,  the largest one occurring in the solution  (691, 37).  Of the 32 solutions for  r = 3,  eight also accept  r = 4.  Of these, in turn, two are solutions for  r = 5,  but not for  r = 6.  These exceptional pairs are  (487, 3)  and  (971, 3).  Note the striking ratio  32 : 8 : 2  of the frequencies.

Secondly, solutions  (a, p)  may otherwise be exceptional in that the congruence  a ^p-1 = 1 (mod p²)  be also fulfilled when  a  and  p  are interchanged. This is the case for the pairs  (3, 1006003),  (5, 1645333507),  (5, 188748146801),  (83, 4871),  and  (911, 318917)  in our table. Only one such solution with both  a,  p > 1000  is presently known, which is  (2903, 18787)  and was discovered by Maurice Mignotte and Yves Roy in 1992.

A table of solutions of  a ^p-1 = 1 (mod p²)  which includes composite bases  a < 1000  is available from the authors. It covers all  p < 10¹⁰,  giving a total of 2735 solutions  (a, p)  in that range.

This investigation was completed with the publication of the following paper, originally presented to the editors on July 30, 2001.

• W. Keller and J. Richstein, Solutions of the congruence a ^p-1 = 1 (mod p^r ), Math. Comp. 74 (2005), 927-936. MR 2005i:11004.

Recently, Richard Fischer has considerably extended the reported computations, see his web site. For prime bases  a ≤ 61  he reached  p < 1.2 × 10¹³  throughout, and for the range  61 < a < 1000  he covered  p < 2.3 × 10¹²,  at least. This led to 12 new solutions in the table below, which are listed in blue color, with permission.

As a result of these additions, some of the statements above have to be adjusted. The only prime bases  a  without a known solution  p  are now  a = 29, 47, 61, 311, 347, 983.  The largest first occurrence of a solution  p  for a given base  a  is found in the pair  (a, p) = (139, 1822333408543),  which also shows the second largest  p  in the table. The largest  p  appears in the pair  (23, 2549536629329).

On February 6, 2009 we learned from Michael Mossinghoff that he had carried out a complete double-check for a substantial segment of the previously searched regions, as part of a much broader investigation. In fact he covered  a < p < 10¹²  for  a < 100  and  a < p < 10¹¹  for  100 < a < 1000.  As a result, a pair with  a = 607  was detected that was missing in the 2004 paper mentioned above. The corresponding prime  p  was added to our table in red color. Also, previous searches were extended to  p < 10¹⁴  for  a = 3, 5, and 17  (the first Fermat primes). A wealth of related data is found at this site.

It should be noted that Richard Fischer has also searched for solutions with composite bases  a < 1000,  to the same limits given for prime bases. For  p < 10¹⁰, his data were in full agreement with the table by the authors of this page. As of February 18, 2009 he had 204 new solutions with  p > 10¹⁰.

Please address questions about this web page to Wilfrid Keller.

Solutions of  a ^p-1 = 1 (mod p²)  for odd prime bases  a