1
$\begingroup$

Another unproven conjecture is that there are an infinitude of primes that are $1$ less than a power of $2$. If $p=2^{k-1}$ is prime, show that $k$ is an odd integer, except when $k=2$.

Hint: $3|4^{n-1} \:\: \forall \:\: n \geq 1$

Can someone explain how to go about this proof step by step, I'm really confused. Thank you so much!

$\endgroup$
  • $\begingroup$ If $k$ is even, $2^k$ is a power of four. $\endgroup$ – user61527 Mar 14 '14 at 0:43
1
$\begingroup$

Your claim is: If p = 2^k - 1 is a prime number, show that k is an odd integer.

The proof is by contradiction,and it goes like this: assume otherwise that k is not an odd

number. That means k is even. Because it is even, k = 2n for some positive integer n. Thus

substituting 2n for k in the expression of p you get: p = 2^(2n) - 1. But 2^(2n) = 4^n. So

p = 4^n - 1. But you already knew that 3 divides 4^n - 1 for all naturals n. This means 3

divides p, and since p is a prime p must be 3. So 2^k - 1 = p = 3 ==> k = 2. Since k is not

equal to 2, p can't be 3. But then p is a composite number because 1, 3, and p are three

distinct factors of p, contradicting the assumption that it is a prime number. So k must

be odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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