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!

Proof about relatively prime integers.

  1. Apr 22, 2013 #1
    This is not homework. If n is a positive odd integer then
    n and [itex] n+2^k [/itex] are relatively prime. k is a positive integer.
    Lets assume for contradiction that n and [itex] n+2^k [/itex] have a common factor.
    then it should divide their difference but their difference is [itex] 2^k [/itex] and since n is odd it has no factors of 2 so this is a contradiction and they are relatively prime.
  2. jcsd
  3. Apr 22, 2013 #2


    User Avatar
    Science Advisor

    Hey cragar.

    I'm not sure exactly what your lecturer expects, but you might want to write down a prime decomposition for n and the other number and show it in detail.

    The intuition behind your proof is right but I'm not sure if your lecturer will want more.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook