- #1
PsychonautQQ
- 784
- 10
Homework Statement
if gcd(a,b) = 1, show that gcd(ac,b) = gcd(c,b)
Homework Equations
gcd(x,y) = xm + yn for integers n and m
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.
Last edited: