# If $\gcd( a, b ) = 1$, then is it true to say $\gcd( ac, bc ) = c$?

I tried to prove this theorem, but I'm really confused about its correctness.
Let's say

$$\gcd( a, b ) = 1 \Rightarrow am + bn = 1 \text{ where } m, n\in\mathbb Z$$

Then by multiplying both side by $c$, we have: $amc + bnc = c$. From here, is it sufficient to say $c = \gcd( ac, bc )$?
I feel like this proof needs some more explanation, but I can't think of one. Any idea?

Thanks,

• @Peter: You don't need to use \operatorname; \gcd is a supported command. – Arturo Magidin Apr 10 '12 at 3:12
• @Arturo Thanks. It is the $\circ$ vs $\text{o}$ all over again! – Pedro Tamaroff Apr 10 '12 at 3:13

What you have shown is that there is a linear combination of $ac$ and $bc$ that equals $c$. Now, for any $x$, $y$, the gcd of $x$ and $y$ divides any linear combination of $x$ and $y$. In this case, this means that the gcd of $ac$ and $bc$ divides $c$.

You are almost done, but you also need to argue that $c$ divides the gcd of $ac$ and $bc$, to conclude the equality (if $z$ and $w$ are positive, and $z$ divides $w$, and $w$ divides $z$, then they are equal).

But, any linear combination of $ac$ and $bc$ is (obviously) a multiple of $c$ since $c$ divides both $ac$ and $bc$. So we are in fact done.

• Clear enough! I see where I missed now. Thanks a lot ;) – Chan Feb 1 '11 at 6:19

It's the special case $\rm\ (a,b) = 1\$ of the following distributive law for GCDs

LEMMA $\rm\quad (a,b)\ =\ (ac,bc)/c$

Proof $\rm\quad\ d\ |\ a,b\ \iff\ dc\ |\ ac,bc\ \iff\ dc\ |\ (ac,bc)\ \iff\ d|(ac,bc)/c$

The above holds more generally in any domain as long as $\rm\ (ac,bc)\$ exists. See my post here for further discussion of this property and its relationship with Euclid's Lemma.

Generally, $a$ and $b$ can be presented as $a=a_{0}^{n_1} \cdot a_{1}^{n_2} \cdots a_{N}^{n_N}$ and $b=b_{0}^{m_1} \cdot b_{1}^{m_2} \cdots b_{M}^{m_M}$, where $a_0 \cdots a_N$ and $b_0 \cdots b_M$ are prime divisors of $a$ and $b$ respectively, and $n_1 \cdots n_N$ and $m_1 \cdots m_M$ are respective prime powers.

If $gcd(a,b)=1$ then $a$ and $b$ has no common prime divisors: $\forall i,j: a_i \ne b_j$. When you multiply both $a$ and $b$ by $c$, sets $a_0 \cdots a_N$ and $b_0 \cdots b_M$ are updated by prime divisors of $c$: $c_0 \cdots c_P$ if they didn't exist, or power sets are updated if some prime divisors already existed. Since $gcd(ac,bc)$ is composed of only common prime divisors of $ac$ and $bc$, and since the only common prime divisors they have are $c=c_{0}^{p_1} \cdot c_{1}^{p_2} \cdots c_{P}^{p_P}$, then $gcd(ac, bc)$ equals $c$.

Since $\gcd(a,b)=1$, there exist two integer $x$ and $y$ such that $ax+by=1$.

Now, $acx+bcy=c$.

It follows that $\gcd(ac,bc)=c.$

• Another answer covers this. – The Chaz 2.0 Apr 10 '12 at 2:34