Cohen and Selfridge's proof about odd numbers which are neither the sum nor difference of a power of two and a prime 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.
 A: 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.
A: 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.
A: 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!
