1. Not finding help here? Sign up for a free 30min 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!

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

    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...