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 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 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.
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 |