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

    chiro

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




Similar Discussions: Proof about relatively prime integers.
  1. Primes vs. integers (Replies: 7)

Loading...