1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic & Number Theory

  1. May 5, 2008 #1
    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: May 5, 2008
  2. jcsd
  3. May 5, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. May 5, 2008 #3
    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...
  5. May 6, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    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??
  6. May 6, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. May 6, 2008 #6
    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: May 6, 2008
  8. May 6, 2008 #7


    User Avatar
    Science Advisor
    Homework Helper

    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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Modular Arithmetic & Number Theory