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

How do I go about proving this?

If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$. I'm very confused with gcd proofs.

share|cite|improve this question
@nhru it is not quite so trivial as you make it sound, and the allusion to equivalence relations escapes me. – Ittay Weiss Feb 12 '14 at 1:25
@nhru That's not the OP and, further, it is false, e.g. $\,(2,3)=1=(3,4)\,$ but $\,(2,4) = 2 > 1.\ \ $ – Bill Dubuque Mar 2 '14 at 22:23

Using Bezout's Identity:

Since there are $x,y,u,v$ so that $\color{#C00000}{ax+by=1}$ and $\color{#00A000}{au+cv=1}$, we have $$ \begin{align} \color{#C00000}{by}\color{#00A000}{cv} &=\color{#C00000}{(1-ax)}\color{#00A000}{(1-au)}\\ &=1-a(x+u-axu)\\ \color{#0000FF}{a}(x+u-axu)+\color{#0000FF}{bc}vy &=1 \end{align} $$ Therefore, $(\color{#0000FF}{a},\color{#0000FF}{bc})=1$

share|cite|improve this answer
Would the downvoter care to comment? – robjohn Feb 28 '14 at 20:59
I too am curious about the downvote. Btw, why do you rearrange before multiplying the Bezout identities? Perhaps to highlight the interpretation in terms of unit multiplicativity? $ $ i.e. $$\,{\rm mod}\ a\!:\ \ \color{#c00}by\equiv 1\equiv \color{#c00}cv\,\Rightarrow \color{#c00}{bc}yv\equiv 1,\ \ \ {\rm i.e.}\ \ \color{#c00}{b,c}\ \ {\rm unit}\ \Rightarrow\, \color{#c00}{bc}\ \ \rm unit$$ – Bill Dubuque Mar 2 '14 at 21:59
How does $a(x+u-axu)+bcvy=1\implies (a,bc)=1$? – Witiko Jun 9 '15 at 14:57
@Witiko: since it is a linear combination of $a$ and $bc$ that equals $1$. If $a$ and $bc$ had a common factor, that common factor would divide any linear combination of $a$ and $bc$. – robjohn Jun 9 '15 at 16:33

If you know Euclid's Lemma (if $p$ is a prime number and $p$ divides the product $bc$, then either $p$ divides $b$ or $p$ divides $c$), then you can proceed as follows. Let $d=gcd(a,bc)$ and assume, to arrive at a contradiction, that $d>1$. Let $p$ then be a prime number dividing $d$. Then $p$ divides both $a$ and $bc$, and thus either $p$ divides $b$ or it divides $c$. If $p$ divides $b$, then since it also divides $a$, it follows that $p$ divides $gcd(a,b)=1$, which is absurd. Similarly, $p$ dividing $c$ leads to a contradiction.

Remark: this solution avoids considering the entire prime number decomposition for the given numbers. I find it to be a nice little trick that produces clean proofs.

share|cite|improve this answer
Unless the proof of Euclid's lemma uses this result with $a=p$. – Aaron Meyerowitz Apr 9 '14 at 16:02

Since $a, b$ are relatively prime, there exist integers $x, y$ such that $ax + by = 1$. Multiplying both sides of this equation by $c$, we get $$acx + bcy = c.$$ Letting $d = \gcd(a, bc)$, we see from the equation above that since $d$ is a common divisor of $a$ and $bc$, $d$ also divides $c$ by linearity. Then, since every common divisor of two integers also divides their gcd, $d|\gcd(a, c)$. But $\gcd(a, c) = 1$, so $d$ divides $1$. Because the gcd is nonnegative, it follows that $d = \gcd(a, bc) = 1$.

share|cite|improve this answer

We can take as the definition of "$a,b$ are relatively prime" that there are $s,t$ with $1=as+bt$. Then the question becomes: given that $$1=as+bt$$ and $$1=au+cv $$ find $S,T$ with $$1=aS+(bc)T.$$ Multiplying by $1$ is a useful trick/technique for questions of this sort. $$1=au+cv=au+1cv=au+(as+bt)cv$$ so $$1=a(u+scv)+bc(tv).$$

What I like is that uses nothing more than basic properties of rings so the proof is applicable in many rings.

share|cite|improve this answer
  • $\gcd(a,b)=1$ means what about the prime factors common to both $a,b$?
  • same for $\gcd(a,c)$
  • what is the prime decomposition of $bc$ if you know what $b$, $c$ decompose as?

Combine all together...

share|cite|improve this answer

More generally $\ (a,b)(a,c) = (aa,ab,ac,bc) = (a\color{#c00}{(a,b,c)},bc) = (a,bc)\ $ if $\ \color{#c00}{(a,b,c)=1},\ $ where we have applied basic gcd laws (associative, commutative, distributive).

share|cite|improve this answer
You are kind of assuming what you want to prove...(because now those rules need a proof) – chubakueno Feb 12 '14 at 2:22
@chubakueno Not true. Any proof of this will use prior results. But neither this proof (or others posted) "assume what you want to prove". – Bill Dubuque Feb 12 '14 at 2:28

$\gcd(a,b)$ means a and b are relatively prime, this means, there is no other common factor other than 1.

you also know that $$\gcd(a,b) = 2^{\min(a_1,b_1)}.3^{\min(a_2,b_2)}.5^{\min(a_3,b_3)}...$$

Now the 2 equations already imply that $$\min(a_1,b_1) = \min(a_2,b_2)=...= 0$$ (there is no common factor of primes)

also $$\min(a_1,c_1) =\min(a_2,c_2)=... = 0$$

this imply, $$\min(a_1,b_1+c_1)= \min(a_2,b_2+c_2)=...=0$$ as the powers > 0, and adding them cannot be < 0,

This imply a,bc are also relatively prime, hence $$\gcd(a,bc)=2^{\min(a_1,b_1+c_1)}.3^{\min(a_2,b_2+c_2)}...= 1$$

($\min(a,b)$ represents here minimum value of a,b)

share|cite|improve this answer

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.