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?


  • $\begingroup$ @Peter: You don't need to use \operatorname; \gcd is a supported command. $\endgroup$ – Arturo Magidin Apr 10 '12 at 3:12
  • 1
    $\begingroup$ @Arturo Thanks. It is the $\circ$ vs $\text{o}$ all over again! $\endgroup$ – 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.

  • $\begingroup$ Clear enough! I see where I missed now. Thanks a lot ;) $\endgroup$ – 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.$

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

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.