1. Limited time only! Sign up for a free 30min personal 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!

3^n+1 has an odd prime divisor

  1. Feb 11, 2012 #1
    Prove that 3n + 1 has an odd prime divisor for all natural numbers > 1. I tried using order but it didn't really get me anywhere. Would prefer hints rather than complete solutions. Thanks.
     
  2. jcsd
  3. Feb 11, 2012 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    If you can't see how to prove this sort of result, start by playing around with the numbers.

    Work out the values of a few numbers, 32+1, 33+1, 34+1, ... What do you notice about them?
     
  4. Feb 11, 2012 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    welcome to pf!

    hi wsldam! welcome to pf! :smile:
    isn't that another way of saying that 2m can never be of the form 3n + 1 ?
     
  5. Feb 11, 2012 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Re: welcome to pf!

    It is also saying that 3n + 1 is never an odd prime (but that's easy to show).
     
  6. Feb 12, 2012 #5
    solution 1: Do it modulo 8
    solution 2: Do it for m odd (mod 3) and m even (factor 2m-1).
     
  7. Feb 12, 2012 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook