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

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$

• 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

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=as'+cy'$$ find $$S,T$$ with $$1=aS+(bc)T.$$ Multiplying by $$1$$ is a useful trick/technique for questions of this sort. $$1=as+bt=as+\mathbf{1}ct=as+\mathbf{(as'+ct')}bt$$ so $$1=a(s+cst')+bc(tt')\\ \ \ \ \ =a(s'+bs't)+bc(tt').$$

The second formula arises from the first by applying $$(bc)(ss')(tt')$$ or shifting the derivation. A single formula invariant under that permutation is

$$1=(as+bt)(as'+ct')=a(ass'+bts'+cst')+bc(tt').$$

The symmetry is nice but the first formulas are smaller.

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

• The definition of "$a,b$ are relatively prime" is different. If $a,b$ are relatively prime / coprime / co-prime, i.e. $\gcd(a,b)=1$ (greatest common divisor), then by Bézout identity/lemma it follows that there exist $s,t\in\mathbb Z$ such that $as+bt=1$. – user236182 Sep 12 '17 at 14:18

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

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

OP is special case $\ (a,b) = \color{#c00}{\bf 1} = (a,b),\$ so $\,\color{#0a0}{(a,b,c) = 1},\$ thus $\ (a,bc) = \color{#c00}{\bf 1\cdot 1}\$ by above.

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

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