Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A search for Wieferich and Wilson primes


Authors: Richard Crandall, Karl Dilcher and Carl Pomerance
Journal: Math. Comp. 66 (1997), 433-449
MSC (1991): Primary 11A07; Secondary 11Y35, 11--04
DOI: https://doi.org/10.1090/S0025-5718-97-00791-6
MathSciNet review: 1372002
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An odd prime $p$ is called a Wieferich prime if

\begin{equation*}2^{p-1} \equiv 1 \pmod {p^{2}};\end{equation*}

alternatively, a Wilson prime if

\begin{equation*}(p-1)! \equiv -1 \pmod { p^{2}}.\end{equation*}

To date, the only known Wieferich primes are $p = 1093$ and $3511$, while the only known Wilson primes are $p = 5, 13$, and $563$. We report that there exist no new Wieferich primes $p < 4 \times 10^{12}$, and no new Wilson primes $p < 5 \times 10^{8}$. It is elementary that both defining congruences above hold merely (mod $p$), and it is sometimes estimated on heuristic grounds that the ``probability" that $p$ is Wieferich (independently: that $p$ is Wilson) is about $1/p$. We provide some statistical data relevant to occurrences of small values of the pertinent Fermat and Wilson quotients (mod $p$).


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

  • 1. T. Agoh, K. Dilcher and L. Skula, Fermat and Wilson quotients for composite moduli, Preprint (1995).
  • 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}}$, The Messenger of Mathematics 43 (1913-1914), 72-84.
  • 3. B. Berndt, R. Evans and K. Williams, Gauss and Jacobi sums, Wiley-Interscience, to appear.
  • 4. J. M. Borwein and P. B. Borwein, Pi and the AGM, John Wiley & Sons, Inc., 1987. MR 89a:11134
  • 5. S. Chowla, B. Dwork, and R. Evans, On the mod $p^{2}$ determination of $(\begin {smallmatrix}(p-1)/2\\ (p-1)/4 \end {smallmatrix})$, J. Number Theory 24 (1986), 188-196. MR 88a:11130
  • 6. D. Clark, Private communication.
  • 7. M. Coster, Generalisation of a congruence of Gauss, J. Number Theory 29 (1988), 300- 310. MR 89i:11005
  • 8. R. Crandall and B. Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), 305-324. MR 94c:11123
  • 9. R. Crandall, Projects in Scientific Computation, TELOS/Springer-Verlag, Santa Clara, CA, 1994. MR 95d:65001
  • 10. -, Topics in Advanced Scientific Computation, TELOS/Springer-Verlag, Santa Clara, CA, 1995.
  • 11. R. Evans, Congruences for binomial coefficients, Unpublished manuscript (1985).
  • 12. Z. Franco and C. Pomerance, On a conjecture of Crandall concerning the $qx+1$ problem, Math. Comp. 64 (1995), 1333-1336. MR 95j:11019
  • 13. R. H. Gonter and E. G. Kundert, All prime numbers up to 18,876,041 have been tested without finding a new Wilson prime, Preprint (1994).
  • 14. A. Granville, Binomial coefficients modulo prime powers, Preprint.
  • 15. D. E. Knuth, The art of computer programming, Vol.2, Addison-Wesley, Reading, Massachusetts, 2nd ed. 1973. MR 44:3531
  • 16. D. H. Lehmer, On Fermat's quotient, base two, Math. Comp. 36 (1981), 289-290. MR 82e:10004
  • 17. E. Lehmer, On congruences involving Bernoulli numbers and the quotients of Fermat and Wilson, Ann. of Math. 39 (1938), 350-360.
  • 18. R. McIntosh, Private communication.
  • 19. P. Montgomery, New solutions of $a^{p-1} \equiv 1 \pmod {p^{2}}$, Math. Comp. 61 (1991), 361-363. MR 94d:11003
  • 20. J. Pollard, Theorems on factorization and primality testing, Proc.Cambridge Phil. Soc. 76 (1974), 521-528. MR 50:6992
  • 21. P. Ribenboim, 13 lectures on Fermat's last theorem, Springer-Verlag, New York, 1979. MR 81f:10023
  • 22. -, The book of prime number records, Springer-Verlag, New York, 1988. MR 89e:11052
  • 23. V. Strassen, Einige Resultate über Berechnungskomplexität, Jahresber. Deutsch. Math.-Verein. 78 (1976/77), 1-8. MR 55:11713
  • 24. Zhi-Hong Sun and Zhi-Wei Sun, Fibonacci numbers and Fermat's last theorem, Acta Arith. 60 (1992), 371-388. MR 93e:11025
  • 25. D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525-532. MR 22:10945
  • 26. A. Wieferich, Zum letzten Fermat'schen Theorem, J. Reine Angew. Math. 136 (1909), 293-302.
  • 27. H. C. Williams, The influence of computers in the development of number theory, Comput. Math. Appl. 8 (1982), 75-93. MR 83c:10002
  • 28. K. M. Yeung, On congruences for binomial coefficients, J. Number Theory 33 (1989), 1-17. MR 90i:11143

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A07, 11Y35, 11--04

Retrieve articles in all journals with MSC (1991): 11A07, 11Y35, 11--04


Additional Information

Richard Crandall
Affiliation: Center for Advanced Computation, Reed College, Portland, Oregon 97202
Email: crandall@reed.edu

Karl Dilcher
Affiliation: Department of Mathematics, Statistics and Computing Science, Dalhousie University, Halifax, Nova Scotia, B3H 3J5, Canada
Email: dilcher@cs.dal.ca

Carl Pomerance
Affiliation: Department of Mathematics, University of Georgia, Athens, Georgia 30602
Email: carl@ada.math.uga.edu

DOI: https://doi.org/10.1090/S0025-5718-97-00791-6
Keywords: Wieferich primes, Wilson primes, Fermat quotients, Wilson quotients, factorial evaluation
Received by editor(s): May 19, 1995
Received by editor(s) in revised form: November 27, 1995, and January 26, 1996
Additional Notes: The second author was supported in part by a grant from NSERC. The third author was supported in part by an NSF grant.
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society