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

  • 1
    $\begingroup$ 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$. $\endgroup$ – lulu Apr 19 '17 at 17:54
  • $\begingroup$ 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$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.