Cohen and Selfridge's proof about odd numbers which are neither the sum nor difference of a power of two and a prime

Question

In a 1975 paper `Not Every Number is the Sum or Difference of Two Prime Powers', Cohen and Selfridge use covering congruences to prove their Theorem 1, which states that there exists an arithmetic progression of odd numbers which are neither the sum nor difference of a power of two and a prime.

The paper is available here:

http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0376583-0/S0025-5718-1975-0376583-0.pdf

As I understand their explanation, they are claiming that if $M$ satisfies a list of congruences (given on the left-hand side of the table on page 2 of the paper), then for any $n$, there will be a prime $p_i$ which is a factor of $M+2^n$ and a prime $p_j$ which is a factor of $M-2^n$, and then they deduce that $M+2^n$ and $M-2^n$ are not prime.

My difficulty stems from the fact that while I can see that their conclusion that there is a $p_j$ which is a factor of $M-2^n$ is clearly justified, I cannot see how to elimiate the possibility that $M-2^n$ might actually be equal to $p_j$.

I have looked back at the paper of Erdős:

On integers of the form $2^k + p$ and some related problems

which is referenced by Cohen and Selfridge, but have not found that it solves my problem.

To a certain extent, my query might be somewhat academic, since, in Theorem 2 of the Cohen and Selfridge paper, they extend their method and their coverings to prove the existence of two distinct prime factors, but I am curious as to whether I have missed something obvious in Theorem 1.

Answer 1

Selfridge liked to be terse in his papers. Indeed, he enjoyed being cryptic enough to puzzle the reader into doing some work. All the heavy lifting is there but some details are left unsaid. For a minor example "two prime powers" of the title is briefer than what that implies after some thought: " a power of $2$ and a prime power."

Consider the arithmetic progression $M=M_0+jm$ where $M_0=47867742232066880047611079$ and $m= 3\ 5\ 7\ 11\ 13\ 17\ 19\ 31\ 37\ 41\ 61\ 73\ 97\ 109\cdot 151\cdot 241\cdot 257\cdot 331 \approx 3.23\ 10^{28}.$

A claim of the paper is that no member of the sequence can ever be written in any of the forms $M=2^n+p,\ $ $M=2^n-p$ or $M=p-2^n$ with $p$ prime. Equivalently, none of $M-2^n,\ 2^n-M\ ,$ or $M+2^n$ is ever prime. (On the other hand $M$ is prime for $j=0,2,58,60,100$, not that it matters.)

The method is covering congruences. For example $M \equiv 54(109)$ and also $2^{17+36k} \equiv 54(109)$ so $|2^n-M|$ is always a multiple of $109$ when $n\equiv 17(36)$ and hence (we suppose) is not prime. This handles $|2^n-M|$ for just under $3 \%$ of the $n$ values. There are two systems of congruences like this which together show that in all cases $|2^n-M|$ always has a prime divisor in common with $m$ (and hence no larger than $331$) and also that the same is true for $2^n+M.$

The question of the OP is a good one. Just because $|2^n-M|$ is always a multiple of $109$ for $n=17+36k$ does this definitively rule out the difference ever being prime? How do we rule out $|2^n-M|=109$ from ever happening? The probability of this on random grounds is exceedingly low (at least once we rule out small cases.) But that is not a proof.

I'll admit it stumped me for a while. What I realize is the following important fact never explicitly mentioned in the paper: The order of $2 \mod m$ is $720.$ So it suffices to check (for the example above of $109$) the $2 \cdot 720$ non-congruences $2^n \pm M \not \equiv 109(m)$ for $0 \le n \le 719.$ As it turns out, the smallest we ever get is $9172668965027048033033417.$ Not unexpected, but good to know. Actually we only have to check the $40$ cases with $n \equiv17(36).$ Presumably this is no trouble if you access to the awesome power of an IBM 360 computer (actually I don't know how impressive that was in 1975, in a later paper Selfridge was very proud that the computations were done on a programmable HP calculator.) Evidently the various other cases are similar.

Answer 2

John,

I attended the talk by Carl Pomerance today, and I asked your question about the original Erdös paper. He said this was well-known as a minor gap in the Erdös paper, and if I email him he will send me the easy fill.

William C. Jagy

San Diego, CA.

With a cold.

Answer 3

In Section 2 of my talk "Simple ideas for famous problems" (available from http://maths.nju.edu.cn/~zwsun/SimIdea.pdf) given in 1996, you will find a detailed proof of Erdos' result in his 1950 paper published in Summa Brasil. Math. In the proof, an extra congruence $x\equiv 3\pmod{31}$ is used.

In my paper "On integers not of the form $\pm p^a\pm q^b$" [Proc. Amer. Math. Soc., 128(2000), no.4, 997--1002] (available from http://maths.nju.edu.cn/~zwsun/34p.pdf), I introduced a method to avoid a bunch of extra congruences, and used the technique to improve the Cohen-Selfridge work (with a detailed proof).

After reading my 1996 talk material and my 2000 paper in Proc. AMS, you will remove your puzzle definitely!