Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

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.