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


    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


    User Avatar
    Homework Helper

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


    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


    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


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook