Two numbers c and m are called relatively prime if there is

Two numbers c and m are called relatively prime if there is no prime p such that p|c and p|m. Examples: 8 and 45 are relatively prime. Also, 7 and 38 are relatively prime. Conversely, 8 and 42 are not relatively prime since 2|8 and 2|42. Claim: If integers a and b are not relatively prime, then there exist no integer-coefficients x and y such that ax + by = 1.

Solution

Assume such integers,x,y exist so that

ax+by=1

a and b are not relatively prime so there is an integer , g>1

so that

a=mg, b=ng

So, mgx+ngy=1

g(mx+ny)=1

BUt, mx+ny is an integer

So, g|1 and g>1 which is a contradiction

Hence, no such x,y exist