# If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$

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.

-
@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
– Martin Sleziak Sep 28 '14 at 7:14

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$

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

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

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

-

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

-
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

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.

-

$\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)

-