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

1. Mar 14, 2007

smithg86

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. Mar 14, 2007

mjsd

yes, i think so.

3. Mar 14, 2007

smithg86

but how would you prove it to be true?

4. Mar 14, 2007

mjsd

try Euclid's Algorithm...

5. Mar 14, 2007

cristo

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

6. Mar 14, 2007

JasonRox

It's neat that you brought that up.

I saw a proof using this property to show that there are infinitely many primes.

7. Mar 14, 2007

mathwonk

how can there be 5 replies to this question?

the more trivial the inquiry the more replies.

8. Mar 15, 2007

Dragonfall

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.

9. Mar 15, 2007

Moo Of Doom

Duh! Because more people know the answer.