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
Answer
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.
No comments:
Post a Comment