John Selfridge

John Lewis Selfridge (February 17, 1927 – October 31, 2010

Career Selfridge served on the faculties of the University of Illinois at Urbana-Champaign and Northern Illinois University (NIU) from 1971 to 1991 (retirement), chairing the NIU Department of Mathematical Sciences 1972–1976 and 1986–1990. He was executive editor of Mathematical Reviews from 1978 to 1986, overseeing the computerization of its operations. He was a founder of the Number Theory Foundation, which has named its Selfridge prize in his honour.

Research In 1962, he proved that 78,557 is a Sierpinski number; he showed that, when k = 78,557, all numbers of the form k2n + 1 have a factor in the covering set {3, 5, 7, 13, 19, 37, 73}. Five years later, he and Sierpiński conjectured that 78,557 is the smallest Sierpinski number, and thus the answer to the Sierpinski problem. A distributed computing project, Seventeen or Bust, is devoted to finding a computational proof of this statement.

In 1964, Selfridge and Alexander Hurwitz proved that the 14th Fermat number was composite.

However, their proof did not provide a factor. It was not until 2010 that the first factor of the 14th Fermat number was found.

In 1975 John Brillhart, Derrick Henry Lehmer, and Selfridge developed a method of proving the primality of p given only partial factorizations of p − 1 and p + 1.

Together with Samuel Wagstaff they also all participated in the Cunningham project.

Together with Paul Erdős, Selfridge solved a 150-year-old problem, proving that the product of consecutive numbers is never a power. It took them many years to find the proof, and John made extensive use of computers, but the final version of the proof requires only a modest amount of computation, namely evaluating an easily computed function f(n) for 30,000 consecutive values of n. Selfridge suffered from writer's block and thanked "R. B. Eggleton for reorganizing and writing the paper in its final form".

Conjecture about Fermat numbers Selfridge made the following conjecture about the Fermat numbers Fn = 22n + 1 . Let g(n) be the number of distinct prime factors of Fn . As to 2024, g(n) is known only up to n = 11, and it is monotonic. Selfridge conjectured that contrary to appearances, g(n) is not monotonic. In support of his conjecture he showed a sufficient (but not necessary) condition for its truth is the existence of another Fermat prime beyond the five known (3, 5, 17, 257, 65537).

Conjectured primality test

This conjecture is also called the PSW conjecture, after Selfridge, Carl Pomerance, and Samuel Wagstaff.

Let p be an odd number, with p ≡ ± 2 (mod 5). Selfridge conjectured that if

2p−1 ≡ 1 (mod p) and at the same time fp+1 ≡ 0 (mod p), where fk is the kth Fibonacci number, then p is a prime number, and he offered $500 for a counterexample. He also offered $20 for a proof that the conjecture was true. The Number Theory Foundation will now cover this prize. A counterexample will actually earn its discoverer $620, because Samuel Wagstaff offers $100 for a counterexample or a proof, and Carl Pomerance offers $20 for a counterexample and $500 for a proof. Selfridge requires that a factorization be supplied, but Pomerance does not. The related test that fp−1 ≡ 0 (mod p) for p ≡ ±1 (mod 5) is unsound: the smallest counterexample for p ≡ 1 (mod 5) is 6601 = 7 × 23 × 41 and the smallest for p ≡ −1 (mod 5) is 30889 = 17 × 23 × 79. Pomerance has given a heuristic argument suggesting that Selfridge's conjecture is likely to be false (i.e. that a counterexample is likely to exist).