Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Solutions of the congruence $a^{p-1} \equiv 1 \pmod {p^r}$


Authors: Wilfrid Keller and Jörg Richstein
Journal: Math. Comp. 74 (2005), 927-936
MSC (2000): Primary 11A07; Secondary 11D61, 11--04
DOI: https://doi.org/10.1090/S0025-5718-04-01666-7
Published electronically: June 8, 2004
MathSciNet review: 2114655
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: To supplement existing data, solutions of $a^{p-1} \equiv 1 \pmod {p^2}$ are tabulated for primes $a, p$with $100 < a < 1000$ and $10^4 < p < 10^{11}$. For $a < 100$, five new solutions $p > 2^{32}$ are presented. One of these, $p = 188748146801$ for $a = 5$, also satisfies the ``reverse'' congruence $p^{a-1} \equiv 1 \pmod {a^2}$. An effective procedure for searching for such ``double solutions'' is described and applied to the range $a < 10^6$, $p <\max\, (10^{11}, a^2)$. Previous to this, congruences $a^{p-1} \equiv 1 \pmod {p^r}$ are generally considered for any $r \ge 2$ and fixed prime $p$ to see where the smallest prime solution $a$ occurs.


References [Enhancements On Off] (What's this?)

  • 1. M. Aaltonen and K. Inkeri, Catalan's equation $x^p - y^q = 1$ and related congruences, Math. Comp. 56 (1991), 359-370. MR 91g:11025
  • 2. N. G. W. H. Beeger, Quelques remarques sur les congruences $r^{p-1} \equiv 1 \pmod{p^2}$ et $(p-1)! \equiv -1 \pmod{p^2}$, Messenger of Math. 43 (1914), 72-84.
  • 3. D. Bressoud and S. Wagon, A course in computational number theory, Key College Publishing, Emeryville, CA, 2000. MR 2001f:11200
  • 4. 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
  • 5. R. Brown, electronic mail dated 13 June 2001.
  • 6. R. Crandall, K. Dilcher, and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433-449. MR 97c:11004
  • 7. A. Cunningham, Period-lengths of circulates, Messenger of Math. 29 (1900), 145-179.
  • 8. R. Ernvall and T. Metsänkylä, On the $p$-divisibility of Fermat quotients, Math. Comp. 66 (1997), 1353-1365. http://users.utu.fi/taumets/fermat/fermat.htm. MR 97i:11003
  • 9. Y. Gallot, Proth.exe: A Windows program for finding very large primes, http://www.utm.edu /research/primes/programs/gallot/.
  • 10. K. Inkeri, On Catalan's conjecture, J. Number Theory 34 (1990), 142-152. MR 91e:11030
  • 11. W. Keller, New prime solutions $p$ of $a^{p-1} \equiv 1 \pmod{p^2}$, Abstracts Amer. Math. Soc. 9 (1988), 503.
  • 12. W. Keller and J. Richstein, Fermat quotients $q_p(a)$ that are divisible by $p$, http://www. informatik.uni-giessen.de/cnth/FermatQuotient.html.
  • 13. J. Knauer and J. Richstein, The continuing search for Wieferich primes, Math. Comp., to appear.
  • 14. R. McIntosh, electronic mail dated 23 February 2001.
  • 15. W. Meissner, Über die Lösungen der Kongruenz $x^{p-1} \equiv 1 \bmod {p^m}$ und ihre Verwertung zur Periodenbestimmung mod $p^\kappa$, Sitzungsber. Berliner Math. Ges. 13 (1914), 96-107.
  • 16. W. F. Meyer, Ergänzungen zum Fermatschen und Wilsonschen Satze, Arch. Math. Physik (3) 2 (1902), 141-146.
  • 17. M. Mignotte and Y. Roy, L'équation de Catalan, Prépubl. de l'IRMA 513/P-299, Université Louis Pasteur et CNRS, Strasbourg, 1992.
  • 18. P. L. Montgomery, New solutions of $a^{p-1} \equiv 1 \pmod{p^2}$, Math. Comp. 61 (1993), 361-363. MR 94d:11003
  • 19. P. Ribenboim, The new book of prime number records, 3rd ed., Springer-Verlag, New York, 1996. MR 96k:11112
  • 20. H. Riesel, Note on the congruence $a^{p-1} \equiv 1 \pmod{p^2}$, Math. Comp. 18 (1964), 149-150. MR 28:1156
  • 21. Worms de Romilly, Équation $a^{p-1} = 1\, +\, $mult. $p^2$, L'Intermédiaire des Math. 8 (1901), 214-215.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11A07, 11D61, 11--04

Retrieve articles in all journals with MSC (2000): 11A07, 11D61, 11--04


Additional Information

Wilfrid Keller
Affiliation: Universität Hamburg, 20146 Hamburg, Germany
Email: keller@rrz.uni-hamburg.de

Jörg Richstein
Affiliation: Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia B3H 3J5, Canada
Email: joerg@mathstat.dal.ca

DOI: https://doi.org/10.1090/S0025-5718-04-01666-7
Keywords: Fermat quotient, Diophantine equation, primitive roots, large primes
Received by editor(s): July 30, 2001
Received by editor(s) in revised form: September 1, 2003
Published electronically: June 8, 2004
Additional Notes: The second author was supported by the Killam Trusts.
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society