1) Suppose 2^k + 1 is a prime number. Prove that k has no prime divisors other than 2. (Hint: if k=ab with b odd, consider 2^k + 1 modulo 2^a +1) First of all, I have a little question. k=ab with b odd. Is this always possible for any natural number k? Why? Assuming it's always possible: (I am using ...=... (mod ..) to mean congruence) 2^k = (2^a)^b =(-1)^b = -1 (mod 2^a + 1) since b is odd => 2^k + 1 = 0 (mod 2^a +1) => 2^k +1 is divisible by 2^a +1 => 2^a +1 = 1 OR 2^a +1 = 2^k +1 (since 2^k +1 is a prime) => 2^a = 0 OR 2^a = 2^ k And I am stuck here, what's next? Thank you!