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

Main Question or Discussion Point

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

Related Linear and Abstract Algebra News on Phys.org
mjsd
Homework Helper
yes, i think so.

but how would you prove it to be true?

mjsd
Homework Helper
try Euclid's Algorithm...

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.

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

mathwonk
Homework Helper
how can there be 5 replies to this question?

the more trivial the inquiry the more replies.

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.

the more trivial the inquiry the more replies.
Duh! Because more people know the answer.