# 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.

-
If the list means finitely many primes, then take large enough M. Gerhard "Looking Out For The Obvious" Paseman, 2013.01.05 –  Gerhard Paseman Jan 5 '13 at 17:44
@Gerhard Paseman: but the $n$ is not bounded, so I do not see how your argument should work; which (I strongly assume) is why OP only asked for the case of difference (for sum it works fine). –  quid Jan 5 '13 at 17:51
Thanks @quid - your assumption is exactly right. –  John Wordsworth Jan 5 '13 at 17:57
It is not a problem if it is equal to p_j only finitely many times. If it were equal infinitely many times, then that says something about the sequence of numbers n, and presumably the congrunce conditions say that M' - 2^n' is also a multiple of a diferent prime for all but finitely many cases of the problematic sequence. Gerhard "Just Guessing; Haven't Read It" Paseman, 2013.01.05 –  Gerhard Paseman Jan 5 '13 at 20:10

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.

-
Many thanks! That makes me feel much less stupid than I did 24 hours ago, and I am grateful for the useful information about Selfridge's writing style. I will accept this after I have had time to sleep on it, and let my brain convince itself that it understands it all :) –  John Wordsworth Jan 6 '13 at 1:03

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.

-
Many thanks for this, Will! Maybe I should now feel a bit less well-educated for not knowing about this well-known gap. I hope you will let me know of the easy fix. Sorry to hear about the cold. –  John Wordsworth Jan 12 '13 at 0:11
I too would like to see it. –  Aaron Meyerowitz Jan 12 '13 at 6:05
@Aaron, I forwarded a copy of my request of Pomerance to you and John. I do not know his travel plans, but I would expect his answer within the week. –  Will Jagy Jan 13 '13 at 21:06