GCD of successive integers

#coprime#consecutive integers#gcd

Statement

Show that $\gcd(n,n+1)=1$ for all $n$ .

Hint

Any common divisor divides the difference.

Show solutionHide solution

Difference. If $d\mid n$ and $d\mid n+1$ , then $d\mid(n+1)-n=1$ .

Conclusion. $d=1$ , so $\gcd(n,n+1)=1$ .

Generalization. $\gcd(n,n+k)\mid k$ , so $\gcd(n,n+k)=1$ iff no prime dividing $k$ divides $n$ .