• Support PF! Buy your school textbooks, materials and every day products Here!

Modular Arithmetic & Number Theory

  • Thread starter kingwinner
  • Start date
  • #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)


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:

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #3
1,270
0
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...
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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??
 
  • #5
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #6
1,270
0
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...
 
Last edited:
  • #7
Dick
Science Advisor
Homework Helper
26,258
618
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?
 

Related Threads for: Modular Arithmetic & Number Theory

  • Last Post
Replies
2
Views
573
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
23
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
2K
Top