Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Does gcd(n, n+1)=1?

  1. Mar 14, 2007 #1
    is the gcd of two successive integers (n, n+1) always equal to 1? i.e., are two successive integers always coprime? it seems like this is the case, but how would you prove this? (this came up in my logic/proof class, but the professor wouldn't or couldn't prove it - this isn't a HW question.)
     
  2. jcsd
  3. Mar 14, 2007 #2

    mjsd

    User Avatar
    Homework Helper

    yes, i think so.
     
  4. Mar 14, 2007 #3
    but how would you prove it to be true?
     
  5. Mar 14, 2007 #4

    mjsd

    User Avatar
    Homework Helper

    try Euclid's Algorithm...
     
  6. Mar 14, 2007 #5

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    Isn't it pretty obvious? suppose m divides n, then n=jm for some j. But then n+1=jm+1 which is not divisible by m (unless m=1). Thus n and n+1 are coprime.
     
  7. Mar 14, 2007 #6

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    It's neat that you brought that up.

    I saw a proof using this property to show that there are infinitely many primes.
     
  8. Mar 14, 2007 #7

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    how can there be 5 replies to this question?

    the more trivial the inquiry the more replies.
     
  9. Mar 15, 2007 #8
    If this comes from a logic class, then I'm assuming you need to construct a formal proof starting from Peano's axioms, with the "existential introduction/elimination", etc. This proposition should take about 50 lines to prove, if you're lucky.
     
  10. Mar 15, 2007 #9
    Duh! Because more people know the answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Does gcd(n, n+1)=1?
  1. A/n = a^(1/n) (Replies: 7)

Loading...