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.
Thanks in advance
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.
Thanks in advance
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