# Proving a gcd equation: $\gcd(ab,c) \mid \gcd(a,c) \cdot \gcd(b,c)$

How would I be able to prove that $$\gcd(ab,c) \mid \gcd(a,c) \cdot \gcd(b,c)$$

I'm assuming I can start by saying $$\gcd(ab,c) \cdot n = \gcd(a,c) \cdot \gcd(b,c)$$ for some $$n \in Z$$ but I'm not sure how I can represent the $$\gcd$$ value as an integer combination of $$a$$ and $$b$$ to prove that the left side can divide the right side

• Easiest, I think, to use unique factorization and the fact that the order of a prime $p$ in $\gcd (m,n)$ is the lesser of the orders of $p$ in $m,n$. – lulu Apr 19 '17 at 17:54
• Hint: if $d\mid x$ and $d\mid y$, then $\gcd(x,y) = d\cdot \gcd(\frac xd,\frac yd)$. Apply this fact with $d=\gcd(a,c)$ and $x=ab$ and $y=c$. – Greg Martin Apr 19 '17 at 18:11

From $\gcd(ab,c)$, we conclude that $\gcd(ab,c) \mid ab$ and $\gcd(ab,c) \mid c$. Now we will have two cases:
Case 1: $\gcd(ab,c) \mid a$ and $\gcd(ab,c) \mid c$:
In this case, we see that $\gcd(ab,c)$ is a common divisor of $a$ and $c$, so by definition of gcd, we have $\gcd(ab,c) \mid \gcd(a,c)$.
Case 2: $\gcd(ab,c) \mid b$ and $\gcd(ab,c) \mid c$:
Similarly, in this case we have $\gcd(ab,c)$ to be a common divisor of $b$ and $c$, so $\gcd(ab,c) \mid \gcd(b,c)$.
In either case, we will have $\gcd(ab,c) \mid \gcd(a,c) \cdot \gcd(b,c)$, and we are done.