If a is any positive integer prove that gcdaa1 1 ie consecu

If a is any positive integer, prove that gcd(a,a+1) = 1. (i.e consecutive positive integers are relatively prime) (hint: assume , for contradiction , gcd(a,a+1)=d , where d>1)

Solution

Let a and b two be a given integer, we first claim that gcd(a, b) = gcd(a, b a).

Infact, we have

gcd(a, b) = gcd(a, b),

= gcd(a, a + (b)),

= gcd(a, a b);

= gcd(a, (a b))

= gcd(a, b a).

In particular, gcd(a, a + 1) = gcd(a,(a + 1) a) = gcd(a, 1) = 1, Proved