zbMATH — the first resource for mathematics

A Wieferich prime search up to $$6.7 \times 10^{15}$$. (English) Zbl 1278.11003
Summary: A Wieferich prime is a prime $$p$$ such that $$2^{p-1} \equiv 1 \pmod{p^2}$$. Despite several intensive searches, only two Wieferich primes are known: $$p = 1093$$ and $$p = 3511$$. This paper describes a new search algorithm for Wieferich primes using double-precision Montgomery arithmetic and a memoryless sieve, which runs significantly faster than previously published algorithms, allowing us to report that there are no other Wieferich primes $$p < 6.7 \times 10^{15}$$. Furthermore, our method allowed for the efficient collection of statistical data on Fermat quotients, leading to a strong empirical confirmation of a conjecture of R. Crandall, K. Dilcher and C. Pomerance [Math. Comput. 66, No. 217, 433–449 (1997; Zbl 0854.11002)]. Our methods proved flexible enough to search for new solutions of $$a^{p-1} \equiv 1\pmod{p^2}$$ for other small values of $$a$$, and to extend the search for Fibonacci-Wieferich primes. We conclude, among other things, that there are no Fibonacci-Wieferich primes less than $$p < 9.7 \times 10^{14}$$.

MSC:
 11-04 Software, source code, etc. for problems pertaining to number theory 11A41 Primes 11Y16 Number-theoretic algorithms; complexity 11Y11 Primality
OEIS
Full Text: