- #1

- 1,270

- 0

**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)

(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!

Last edited: