Let n be an integer determine GCD nn1 by proofsSolutionassum

Let n be an integer, determine GCD (n,n+1), by proofs.

Solution

assume gcd(n,n+1) = k
then n = a*k and n+1 = b*k for some integers a and b
then n+1 = ak+1 = bk
so bk-ak = 1
(b-a)k = 1
There are several (fairly equivalent) arguments from this point
we can say:
b-a = 1/k; and we know b-a is a positive whole number, and k is also a whole number so k =1
Or:
(b-a) and k are whole numbers, and (b-a)k = 1 so k = b-a = 1

so,GCD(n,n+1)=1