# 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

## 1 Answer

Yes, the proofs are fine. You did not do part (d), but it requires nothing new, so it is quite reasonable to omit it. In the formal statement of the lemma, the conditions on the parameters should have been made explicit.

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.

-