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