Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

A search for Wieferich and Wilson primes

Author(s): Richard Crandall; Karl Dilcher; Carl Pomerance.
Journal: Math. Comp. 66 (1997), 433-449.
MSC (1991): Primary 11A07; Secondary 11Y35, 11--04
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

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 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: 10.1090/S0025-5718-97-00791-6
PII: S 0025-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.
Copyright of article: Copyright 1997, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google