If $a,b, c \in \mathbb{Z}$, then $c ·\gcd(a,b) ≤ gcd(ca, cb)$.

Question

If $a,b, c \in \mathbb{Z}$, then $c ·\gcd(a,b) ≤ \gcd(ca, cb)$.

Im looking for a proof of this question. I see some of the pieces but I have no idea how to approach this question. It is supposed to be answered with direct proof. I have already looked at it for an hour and its due on friday. I have no access to any other help, so I am desperate. Any help will be much appreciated :)

Answer 1

To show that something is less than the greatest common divisor of $ca$ and $cb$, it is enough to show that is a common divisor of $ca$ and $cb$, since obviously the $\gcd$ is the greatest divisor.

Now, $\gcd(a,b)$ divides $a$, hence $c \times \gcd(a,b)$ divides $c a$. Similarly, it divides $cb$. Hence, $c \times \gcd(a,b)$ is a common divisor of $ca$ and $cb$, so it's smaller than the greatest common divisor, which is $\gcd(ca,cb)$.

Moreover, $c \gcd(a,b)$ is a divisor of $\gcd(ca,cb)$, in fact. This follows from the fact that for any two common divisors of $ca$ and $cb$, their least common multiple is also a divisor of $ca$ and $cb$.

Answer 2

$gcd(a,b)$ divides $a$ implies $cgcd(a,b)$ divides $ca$ since ${ca\over cgcd(a,b)}={a\over {gcd(a,b)}}$, $cgcd(a,b)$ divides $cb$ so $cgcd(a,b)$ is a divisor of $ca$ and $cb$ and by definition is inferior to $gcd(ca,cb)$.

Answer 3

Let $ d= gcd(a,b) $ then $ d $ divides $ a $ and $ d $ divides $ b $. Moreover, if $ d' $ divides $ a $ and $ b $ we have that $ d' \le d $. Now, $ d $ divides $ a $ implies $ cd $ divides $ ca $. Analogously, $ cb $. Thus,by difinition, $ cd \le gcd(ca,cd) $.