1. The problem statement, all variables and given/known data if gcd(a,b) = 1, show that gcd(ac,b) = gcd(c,b) 2. Relevant equations gcd(x,y) = xm + yn for integers n and m 3. The attempt at a solution ax + by = 1 gcd(ac,b) = d gcd(c,b) = g ac = dr b = ds c = gm b = gn I've been setting up equations and rearranging things but can't make any leeway, any tips? Update: g|c and g|b, so g|ac and hence g|d. d|ac and d|b. If I can show that d|c then i can conclude d|g. hence d=g. I now need help showing that d|c.