# Thread: Probably an easy gcd proof

1. ## Probably an easy gcd proof

I have to prove that if a and b are relatively prime, gcd(ac,b) = gcd(c,b)

This is simple enough if you use the idea of prime factorization, but i've been specifically instructed not to resort to prime factorization.

2. Originally Posted by Ryan
I have to prove that if a and b are relatively prime, gcd(ac,b) = gcd(c,b)

This is simple enough if you use the idea of prime factorization, but i've been specifically instructed not to resort to prime factorization.

since gcd(a,b)=1

qa+wb=1

assume gcd(c,b)=d

then

ec+rb=d

ec*1+rb=d

ec*(qa+wb)+rb=d

(eq)(ac)+(ecw)b+rb=d

(eq)(ac)+((ecw)+r)b=d

also note:gcd(ac,b)>=gcd(c,b)

3. First off, thanks

I follow what you've done but how do we know that d is necessarily the greatest common divisor of ac and b? I'm assuming I need to use the fact that gcd(ac,b)>=gcd(c,b) but I'm not quite sure where to go with that

4. First, we know that gcd(c,b)=d

and that gcd(ac,b)>=gcd(c,b) (do you believe this)

we found a linear combination of ac and b such that it equaled d.

therefore gcd(ac,b)<=d (we might be able to find a positive l.c. of ac and b that is less than d) but we can't since

d>=gcd(ac,b)>=gcd(c,b)=d

5. Now I follow, this makes perfect sense. I appreciate your help.