Are Two Successive Integers Always Coprime?

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

 

[mjsd]

yes, i think so.

 

[smithg86]

but how would you prove it to be true?

 

[mjsd]

try Euclid's Algorithm...

 

[cristo]

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]

It's neat that you brought that up.

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

 

[mathwonk]

how can there be 5 replies to this question?

the more trivial the inquiry the more replies.

 

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

 

[Moo Of Doom]

the more trivial the inquiry the more replies.

Duh! Because more people know the answer.