- #1
kingwinner
- 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)
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!
(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: