# Is this proof about the form $2^n \pm a$ correct?

I want to prove following statement :

For prime numbers $p$ greater than $3$, it is true that:

$a)$ if $p=2^n-a$ and $a=6k+1$, then $n$ is an odd number.

$b)$ if $p=2^n+a$ and $a=6k-1$, then $n$ is an odd number.

$c)$ if $p=2^n-a$ and $a=6k-1$, then $n$ is an even number.

$d)$ if $p=2^n+a$ and $a=6k+1$, then $n$ is an even number.

where $n \in \mathbf{Z}^+, k\in \mathbf{Z}^\ast$.

Proof :

$a)$ Lemma $1$ : $a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+....+b^{n-1})$

$p=2^n-(6k+1)=2(2^{n-1}+1)-6k-3=2(2^{n-1}+1)-3(2k+1)$

Let's suppose that $n$ is even then $n-1$ is odd and by the Lemma $1$:

$(2+1) \mid (2^{n-1}+1)$ and since $(2+1) \mid 3(2k+1)$ we may conclude that $p$ is composite number.

So, we have contradiction, therefore $n$ must be odd number.

$b)$ Similarly as case $a)$

$c)$ $p=2^n-(6k-1)=2(2^{n-1}-1)-6k+3=2(2^{n-1}-1)-3(2k-1)$

let's suppose that $n$ is odd then $n-1$ is even ,therefore

$2^{n-1}-1=2^{2t}-1=(2^t-1)(2^t+1)$ , so :

$3 \mid (2^{n-1}-1)$ and since $3 \mid 3(2k-1)$ we may conclude that $p$ is composite number.

So,we have contradiction,therefore $n$ must be even number.

$d)$ Similarly as case $c)$

Is this an acceptable proof?

-
Your Lemma 1 in part (a) is only true when $n$ is odd, by the way. But that's how you use it, so no problem. Although your proof seems sound, it's probably more elegant to phrase things in terms of congruences modulo 3. –  Greg Martin Nov 14 '11 at 5:54

You chose to avoid congruence notation. I would probably instead observe first that $2^n \equiv 1 \pmod{3}$ if $n$ is even, and $2^{n}\equiv -1\pmod{3}$ if $n$ is odd. This can be proved in the style that you used, or more neatly by using properties of congruences: since $2\equiv -1\pmod{3}$, it follows that $2^n \equiv (-1)^n \pmod{3}$.
Then for example for (b), if $n$ is odd, and $a\equiv -1\pmod{6}$, then $2^n+a\equiv 1+(-1)=0\pmod{3}$. If we wish, we can even gather all four results together into one.
For divisibility of $2^n \pm 1$ by $3$, congruence language has no advantage over the techniques that you used. For more complicated situations, congruence language becomes more and more essential.