Fermat quotients  qp(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  qp(a) = (a p-1 - 1) / p  is called the Fermat quotient of  p  with base  a.  The number  qp(a)  may again be divisible by  p.  This is equivalent to saying that the congruence  a p-1 = 1 (mod p2)  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 < 1011.  For the particular bases  a = 3  and  a = 5  the larger interval  p < 1013  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.

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 pr)  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 p2)  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  ap > 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 p2)  which includes composite bases  a < 1000  is available from the authors. It covers all  p < 1010,  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.

Recently, Richard Fischer has considerably extended the reported computations, see his web site. For prime bases  a ≤ 61  he reached  p < 1.2 × 1013  throughout, and for the range  61 < a < 1000  he covered  p < 2.3 × 1012,  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 < 1012  for  a < 100  and  a < p < 1011  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 < 1014  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 < 1010, 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 > 1010.

Please address questions about this web page to Wilfrid Keller.

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

a     Values of  p
3     11, 1006003
5     20771, 40487, 53471161, 1645333507, 6692367337, 188748146801
7     5, 491531
11     71
13     863, 1747591
17     3, 46021, 48947, 478225523351
19     3, 7, 13, 43, 137, 63061489
23     13, 2481757, 13703077, 15546404183, 2549536629329
29     None
31     7, 79, 6451, 2806861
37     3, 77867, 76407520781
41     29, 1025273, 138200401
43     5, 103
47     None
53     3, 47, 59, 97
59     2777
61     None
67     7, 47, 268573
71     3, 47, 331
73     3
79     7, 263, 3037, 1012573, 60312841
83     4871, 13691, 315746063
89     3, 13
97     7, 2914393, 76704103313
101     5, 1050139
103     24490789
107     3, 5, 97, 613181
109     3, 20252173
113     405697846751
127     3, 19, 907, 13778951
131     17, 754480919
137     29, 59, 6733, 18951271, 4483681903
139     1822333408543
149     5, 29573, 121456243, 2283131621
151     5, 2251, 14107, 5288341, 15697215641
157     5, 122327, 4242923, 5857727461, 275318049829
163     3, 3898031
167     64661497
173     3079, 56087
179     3, 17, 35059, 126443
181     3, 101
191     13, 379133
193     5, 4877
197     3, 7, 653, 6237773
199     3, 5, 77263, 1843757
211     279311
223     71, 349
227     7, 40277
229     31
233     3, 11, 157, 86735239
239     11, 13, 74047, 212855197, 361552687, 12502228667
241     11, 523, 1163, 35407
251     3, 5, 11, 17, 421, 395696461
257     5, 359, 49559, 648258371
263     7, 23, 251, 267541, 159838801
269     3, 11, 83, 8779, 65684482177
271     3, 168629, 16774141, 235558417, 12145092821
277     1993, 243547988443
281     3443059
283     46301
293     5, 7, 19, 83
307     3, 5, 19, 487
311     None
313     7, 41, 149, 181, 1259389
317     107, 349, 2227301
331     211, 359, 6134718817
337     13, 30137417
347     None
349     5, 197, 433, 7499
353     8123, 465989, 17283818861
359     3, 23, 307, 24350087
367     43, 2213
373     7, 113
379     3
383     28067251
389     19, 373, 29569, 211850543
397     3, 279421, 13315373041
401     5, 83, 347, 115849
409     34583, 1894600969
419     173, 349, 983, 3257, 22891217
421     101, 1483, 350677, 1083982004309
431     3, 2393, 12755833
433     3, 129497, 244403
439     31, 79, 170899693
443     5, 3406223
449     3, 5, 1789
457     5, 11, 919, 1589513
461     1697, 5081
463     1667
467     3, 29, 743, 7393
479     47, 2833, 500239
487     3, 11, 23, 41, 1069
491     7, 79, 661763933, 121261604419
499     5, 109, 81307, 24117560837
503     3, 17, 229, 659, 6761
509     7, 41, 7215975149
521     3, 7, 31, 53, 8938997
523     3, 9907, 19289
541     3
547     31, 1691778551
557     3, 5, 7, 23, 39829
563     18920521
569     7, 263, 25359067
571     23, 29, 308383
577     3, 13, 17, 71, 1381277
587     7, 13, 31, 22091, 6343317671
593     3, 5
599     5, 35771
601     5, 61
607     5, 7, 40303229, 22035814429
613     3, 4073, 81371669, 18419352383
617     101, 1087, 6007
619     7, 73, 11682481, 52649183399
631     3, 1787, 5741
641     43, 24481
643     5, 17, 307, 859, 460609, 7354807
647     3, 23, 15266862761
653     13, 17, 19, 1381, 22171, 637699
659     23, 131, 2221, 9161, 65983
661     441583073, 462147547073
673     61
677     13, 211
683     3, 1279
691     37, 509, 1091, 9157, 84131, 10843045487, 312679516579
701     3, 5
709     17, 199, 1663
719     3, 41, 4414200313
727     11
733     17
739     3, 9719, 5681059
743     5
751     5, 151, 409
757     3, 5, 17, 71, 242789
761     41, 907
769     1305827821
773     3, 787711, 26259199, 142719149
787     37, 41, 427541
797     8273, 14607661
809     3, 59, 448110371
811     3, 211
821     19, 83, 233, 293, 1229, 37871, 209140301
823     13, 2309
827     3, 17, 29, 9323
829     3, 17
839     5227, 11840951
853     1125407
857     5, 41, 157, 1697, 32478247
859     71
863     3, 7, 23, 467, 12049
877     78926821
881     3, 7, 23, 22385723, 94626144313
883     3, 7
887     11, 607, 60623
907     5, 17, 3497891
911     127, 318917
919     3
929     62199604679
937     3, 41, 113, 853, 22343, 500861, 1031299, 258469889
941     11, 1499
947     5021
953     3, 513405611, 220564434997, 1082305363079
967     11, 19, 4813, 44830663
971     3, 11, 401, 9257, 401839, 7672759
977     11, 17, 109, 239, 401, 37589
983     None
991     3, 13, 431, 26437
997     197, 1223


Last modified: February 22, 2009.