5
$\begingroup$

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 !

Thanks in advance !

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Maman Sep 17 '16 at 17:09
  • $\begingroup$ @Maman Yes, but it's too much work! ;-) $\endgroup$ – egreg Sep 17 '16 at 17:12
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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