Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was surprised to discover that $32$, $128$, $512$, and $2048$ cannot be represented in this way, and I've since found that the same is true for $8192$, $32768$, $131072$, $524288$, $2097152$, and $8388608$. Is there any counterexample? If not, how can it be proved?

share|cite|improve this question
up vote 9 down vote accepted

From Nicolas's argument I realized that it was sufficient to check if $2^{2n+1}-7$ was prime. A much easier task than the usual brute forcing. After a few minutes of manual testing on wolfram alpha I found that $2^{39}$ could indeed be written as the sum of a prime and a safeprime:


Edit: I wrote a sage program to check all of the odd powers of two less than 2000. It seems I was a bit lucky since the next examples are 715 and 1983. I checked OEIS and numbers such that $2^{n}-7$ are prime has its own page.

share|cite|improve this answer
Wow! ........... (39 of these) – Dan Brumleve Sep 14 '11 at 6:50

The congruential argument below shows that we need only worry about the safe prime $7$.

An odd power of $2$ is congruent to $-1$ modulo $3$. Let $p$ be a safe prime. Then, except in the cases $p=5$ and $p=7$, $p$ is of the form $2(6k\pm 1)+1$. But $p$ cannot be of the form $2(6k+1)+1$, so it is of the form $2(6k-1)+1$, that is, $p$ is congruent to $-1$ modulo $3$. The safe prime $5$ is also congruent to $-1$ modulo $3$. (The only safe prime that escapes this congruential net is $7$.)

So if $2^{2n+1}=p+q$, where $p$ is a safe prime other than $7$, then $q$ must be divisible by $3$. In particular, if $q$ is prime, $q$ must be $3$.

But this is not possible, since (apart from the case $p=5$) a safe prime $p$ is congruent to $3$ modulo $4$, and hence $p+3$ is congruent to $2$ modulo $4$. The case $p=5$ accounts for the decomposition $8=5+3$.

Thus if $2^{2n+1}=p+q$, where $p$ and $q$ are primes and $p$ is safe, we must have $p=7$. So the only question that remains is to look for primes $q$ of the form $q=2^{2n+1}-7$.

There likely is some literature on primes of the form $2^{2n+1}-7$. A feeble attempt at experimentation did not locate any, but there is certainly not always a simple small divisor.

share|cite|improve this answer
I have: $2^{2k+1} = q + r$, $r = 2p+1$, $4^k = p + (q+1)/2$. What am I missing? – Dan Brumleve Sep 14 '11 at 6:12
Ahh, got it. Now I wonder if there are any other classes of exceptions that invalidate the heuristic argument I suggested in my answer to the other question? – Dan Brumleve Sep 14 '11 at 6:16
But I guess it is still possible that $2^{2k+1} = 7+q$ for some prime $q$? This is a great answer but I've unaccepted it for the moment. – Dan Brumleve Sep 14 '11 at 6:38
@Dan Brumleve: No problem, easy come easy go. It is not often that simple congruential conditions get us this far. Yes, $7$ is the only possible exception. The weird safe primes are $5$ and $7$, and $5$ was no trouble. – André Nicolas Sep 14 '11 at 6:51
@Dan Brumleve: A little mulling over numbers showed that the difference between $2^{2n+1}$ and a safe prime is usually divisible by $3$. Paid no attention to $7$ since it is obviously special. So had to rule out a difference of $3$ (easy) and $7$ (not easy, indeed as it turns out not possible). – André Nicolas Sep 14 '11 at 7:06

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.