Irregular Primes to One Million (Q4032176)

The authors have calculated the irregular pairs \((p,k)\) for all primes \(p < 10^ 6\). Recall that a pair \((p,k)\) is called irregular if \(k\) is an even integer with \(2 \leq k \leq p-3\) such that \(p\) divides the numerator of the Bernoulli number \(B_ k\). Previous computations of the irregular pairs, covering the range \(p < 150\;000\) [see \textit{J. W. Tanner} and \textit{S. S. Wagstaff}, ibid. 48, 341--350 (1987; Zbl 0613.10012)], used algorithms requiring \(O(p^ 2)\) arithmetic operations for each prime \(p\). The present authors were able to reduce this number to \(O(p\log p)\). They computed Bernoulli numbers modulo \(p\) basically from the formula \[ \sum^ \infty_{k = 0} B_ kx^ k/k! = (1 + x/2! + x^ 2/3! + \dots)^{-1}, \] performing the power series inversion by algorithms based on the fast Fourier transform and multisectioning of power series. The maximum number of irregular pairs \((p,k)\) found in this range was 6, occurring for \(p = 527377\). The authors also used their results to verify that Fermat's ``Last Theorem'' and Vandiver's conjecture are true for the primes \(p < 10^ 6\). \{A subsequent work by the first two authors together with \textit{R. Ernvall} and the reviewer [ibid., July 1993 issue] extends the above calculations to all primes below four million and moreover gives the ordinary cyclotomic invariants for these primes\}.