Modular Arithmetic & Number Theory

[kingwinner]

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!

 

[Dick]

Little question first. No, it's not possible for any k except in the trivial sense that 1 is odd. The hint is suggesting you use proof by contradiction. Assume k has a prime factor that's not 2. Let b be that factor.

 

[kingwinner]

OK, now I understand the logic of the question, but the work-out still seems to be the same and I am stuck at the same point...

 

[Dick]

Great. So why did you just pass over "=> 2^k +1 is divisible by 2^a +1" in your relentless drive to a state of confusion? 2^k+1 is assumed to be PRIME. Didn't that make you think, even for a second? DO YOU UNDERSTAND WHY GIVING ADVICE CAN GET FRUSTRATING??

 

[Dick]

I really think you are just sleeping while you write these lines. Thinking, "I don't have to think, somebody else will do it for me". I'll just get confused. And ask again, and again and again. You are missing REALLY OBVIOUS POINTS. And don't tell me how badly prepared your curriculum is or how bad the level of instruction. PF is making you intellectually lazy. You might want to lay off the posting for a while and just try a few questions on your own.

 

[kingwinner]

I think there is some delay in displaying my edited version, that's not where I got stuck, I am stuck at "...2^a = 0 OR 2^a = 2^k"

2^a=0 is contradiction
2^a=2^k => a=k. But k=ab => ab=a but b is prime => contradiction

=> k has no prime divisors other than 2 => done!

This is not obvious to me!
And I am doing hundreds of practice problems this week, and I am only stuck on a few and post it here to see if someone can help! I am not lazy...

 

[Dick]

I think there is some delay in displaying my edited version, that's not where I got stuck, I am stuck at "...2^a = 0 OR 2^a = 2^k"

2^a=0 is contradiction
2^a=2^k => a=k. But k=ab => ab=a but b is prime => contradiction

=> k has no prime divisors other than 2 => done!

This is not obvious to me!
And I am doing hundreds of practice problems this week, and I am only stuck on a few and post it here to see if someone can help! I am not lazy...

I didn't mean you were lazy. I meant you are overdependent on getting a hint before you start thinking. The above looks fine. it's obvious to you now, right?