# Prove that if $\gcd(a,b)=\gcd(b,c)=\gcd(a,c)=1$ then $\gcd(bc,ac,ab)=1$?

So I write 3 Bézout's identities :

$au+bv=1$

$bv+cw=1$

$au+cw=1$

We could have taken different $u,v,w$...

By multiplying I obtain :

$1=ab(v^2ub+u^2va+uvwc)+ac(w^2uc+u^2wa+uvwb)+bc(v^2wb+w^2vc)$

By taking : $v^2ub+u^2va+uvwc=x \in \mathbb{Z}, \ w^2uc+u^2wa+uvwb=y\in\mathbb{Z}, \ v^2wb+w^2vc=z\in\mathbb{Z}$ then $\gcd(bc,ac,ab)=1$.

Now I want to generalize it to a product of $n$ terms without the $i^{th}$ term. Are there any faster methods than developing ?

PS : This statement is a key to start the proof of the CRT !

Suppose a prime $p$ divides $\gcd(bc,ac,ab)$; then $p\mid (bc)$, so it either divides $b$ or it divides $c$, but not both because $\gcd(b,c)=1$.

Suppose $p\mid b$ and $p\nmid c$. Since $p\mid ac$, we conclude $p\mid a$, contradicting $\gcd(a,b)=1$.

Similarly, assuming $p\nmid b$ and $p\mid c$ leads to a contradiction, by considering that $p\mid ab$.

Can we generalize it to more than three numbers? Suppose $a_1,a_2,\dots,a_n$ are pairwise coprime. Set $$c_i=\frac{a_1a_2\dots a_n}{a_i}$$ Then $\gcd(c_1,c_2,\dots,c_n)=1$.

Indeed, if $p$ is a prime divisor of $\gcd(c_1,c_2,\dots,c_n)=1$. Then $p\mid c_n$, so $p$ divides exactly one of $a_1,\dots,a_{n-1}$. Without loss of generality we can say that $p\mid a_1$; since also $p\mid c_1$, we get a contradiction, because by assumption $\gcd(a_1,a_j)$ for $j>1$.

Actually, this is a distributive lattice property. Let's consider \begin{align} (b\lor c)\land (a\lor c)\land(a\lor b) &=(b\lor c)\land\bigl(a\lor(b\land c)\bigr)\\ &=\bigl((b\lor c)\land a)\lor(b\land c)\\ &=(a\land b)\lor(a\land c)\lor(b\land c) \end{align} and, if $a\land b=a\land c=b\land c=\mathbf{0}$, then also $$(b\lor c)\land (a\lor c)\land(a\lor b)=\mathbf{0}$$ (where $\mathbf{0}$ denotes the minimum element of the lattice). Here the distributive lattice is the natural numbers under divisibility, where the minimum is $1$, $\land$ is the gcd and $\lor$ is the lcm.

• Ok so you use Euclid's lemma. I was confused with this lemma because there were too many terms. Does my proof with Bézout in the case of 3 numbers is right ? – Maman Sep 17 '16 at 17:09
• @Maman Yes, but it's too much work! ;-) – egreg Sep 17 '16 at 17:12

$gcd (a,b). = gcd (b,c) = gcd (c,a) =1$ means a,b,c do not have any common prime factors among them.

So $gcd (ab,bc) = b$ and since a,c do not have any factors of b, their $gcd(b,ca)=1$

This is straightforward if you use the properties of $gcd()$. I have written out the detailed steps. $$1\le gcd(bc, ac, ab) = gcd(gcd(bc, ac), ab) =gcd(c*gcd(b, a), ab) = gcd(c, ab) \le gcd(c, a) * gcd(c, b)=1*1=1,$$ So $gcd(bc, ac, ab)=1$.

To extend this to $n\ge 3$ variables $x_1$, ..., $x_n$, the idea is the same plus induction. Let $s=x_1...x_{n+1}$. $$1\le gcd(\frac{s}{x_1}, ..., \frac{s}{x_{n+1}}) = gcd(x_{n+1}gcd(...), \frac{s}{x_{n+1}}) = gcd(x_{n+1}, x_1...x_n) \le gcd(x_{n+1}, x_1)...gcd(x_{n+1}, x_n)= 1*...*1=1$$

$$au+bv=1 \Rightarrow acu+bcu=c \Rightarrow gcd(ac,bc) |c \Rightarrow gcd(ac,bc, ab) |c$$

Same way $gcd(ac,bc, ab) |b$.

Then $gcd(ac,bc, ab)$ is a common divisor of $b$ and $c$. As $gcd(b,c)=1$ you get $$gcd(ac,bc, ab) =1$$