Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
@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
up vote 13 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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$.

share|cite|improve this answer

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.$

share|cite|improve this answer
Another answer covers this. – The Chaz 2.0 Apr 10 '12 at 2:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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