MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been running a computer program trying to see if I can represent any odd number in the form of

$$2^a - b$$

With b as a prime number. I have seen an earlier proof about Cohen and Selfridge regarding odd numbers that are nether a sum or a difference of a power of two and a prime, and I was curious to see if anyone has found an odd number that couldn't be represented using the above formula.

share|cite|improve this question

Fred Cohen and J. L. Selfridge, Not Every Number is the Sum or Difference of Two Prime Powers contains an example of such a number:

Corollary: 47867742232066880047611079 is prime and neither the sum nor difference of a power of two and a prime.

share|cite|improve this answer

Erdos's argument essentially gives that there is an infinite arithmetic progression of odd numbers containing no element of the form power of two minus a prime.


\begin{array}{cccc} i & a_i & m_i & p_i \\ 1 & 1 & 2 & 3 \\ 2 & 2 & 4 & 5 \\ 3 & 4 & 8 & 17 \\ 4 & 8 & 16 & 257 \\ 5 & 16 & 32 & 65537 \\ 6 & 0 & 64 & 641 \\ 7 & 32 & 64 & 6700417 \\ \end{array}

Set $A_0=\{x:x\equiv 1 \pmod{8}\}$, $A_i=\{x:x\equiv 2^{a_i} \pmod{p_i}\}$ ($1\leq i\leq 7$), $B=A_0\cap A_1\cap\cdots\cap A_7$.

$B$ is an AP consisting of odd numbers. Assume that $x\in B$ and $x=2^n-q$ for some odd prime $q$. For some $1\leq i\leq 7$, we have $n\equiv a_i \pmod{m_i}$, therefore $x\equiv 2^{a_i}-q \pmod{p_i}$. As $x\in A_i$, we also have $x\equiv 2^{a_i} \pmod{p_i}$, consequently $q=p_i$. But this is impossible as $2^n\equiv 0 \pmod{8}$ for $n\geq 3$, $p_i\equiv 1,3,5 \pmod{8}$ and as $x\in A_0$, $x\equiv 7 \pmod{8}$.

share|cite|improve this answer
This argument comes from the paper in which Erdos introduced covering congruences to an unsuspecting world. – Gerry Myerson Jan 5 '14 at 16:19
This made me wonder, does anyone actually know the smallest odd positive number that cannot be written in the form $2^a-p$. Using covering congruences I can proof that 509203 cannot be written the form $2^a-p$. But I suspect there might be smaller numbers that cannot be written in the form $2^a-p$. If a number is not of the form $2^a-p$ can one always use a covering congruences argument to prove this? – Maarten Derickx Jan 6 '14 at 10:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.