Let a and b be integers Show that if there exist integers x

Let a and b be integers. Show that if there exist integers x and y such that ax + by = 1, then gcd(a , b) = 1.

Solution

Assume,g= gcd(a,b)>1

a=pg, b=qg

ax+by=1

gpx+gqy=1

g(px+qy)=1

x,y,p,q are integers hence, px+qy are integers

Hence, g|1 but g>1

SO, g|1 is not possible

Hence a contradiction

Hence, g=1