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}\).

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