Prove that if $\forall \ i\neq j \in \{1,...,k\}$, $\gcd(n_i,n_j)=1$ then $\gcd(n_1,...,n_k)=1$

Question

I try to prove that statement using only Bachet-Bézout theorem (I know that it's not the best technique). So I get $k$ useful equations with $n_1$ then $(k-1)$ useful equations with $n_2$ ... then $1$ useful equation with $n_{k-1}$. I multiply all these equations to obtain $1$ for one side. For the other side I'm lost (there are too many terms) but I want to make appear the form $n_1 L_1+...+n_k L_k$.

Supposing the existence of all the integers we need :

$\underbrace{(a_1n_1+a_2n_2)(a_1n_1+a_3n_3)...(a_1n_1+a_kn_k)}_{\textit{k equations}} \underbrace{(b_2n_2+b_3n_3)...(b_2n_2+b_kn_k)}_{\textit{(k-1) equations}}...\underbrace{(\mu_{k-1} n_{k_1}+\mu_{k} n_k)}_{\textit{1 equation}}=1$

Maybe we can reduce the number of useful equations or start an induction to identify a better form for the product.

Thanks in advance !

Answer 1

According to the Bachet-Bezout Lemma, the gcd of two integers $gcd(a,b)=d$ is the smallest positive integer that can be written as $ax+by=d$ for some integers $x,y$. We split the discussion into two parts:

If $k$ is even: Then there exists integers $\{x_i\}$ such that $$n_1x_1+n_2x_2=1$$$$n_3x_3+n_4x_4=1$$$$...$$$$n_{k-1}x_{k-1}+n_kx_k=1$$ Just multiply the first equation by $\frac{k}{2}$ and subtract all the rest to get $$\frac{k}{2}\cdot n_1+\frac{k}{2}\cdot n_2+\sum_{i=3}^k (-x_i)\cdot n_i=1 \implies gcd(n_1,n_2...,n_k)=1$$

If $k$ is odd: Arrange $\{n_i\}$ such that $n_1\neq 1$ (this is possible, otherwise all $n_i=1$ and there's nothing to prove). We prove that there exists $\{x_i\}$ such that $$n_1x_1+n_2x_2 + n_3x_3=1$$$$n_4x_4+n_5x_5=1$$$$...$$$$n_{k-1}x_{k-1}+n_kx_k=1$$ The second to last equations exist for some $x$ by Bachet-Bezout, while the first can be achieved with $(x'_2,x'_3)$ such that $$n_2x'_2+n_3x'_3=1$$ and setting $(x_1,x_2,x_3)=(1,(-n_1+1)x'_2,(-n_1+1)x'_3)$. Hence, similar to above, we multiply the first equation by $\frac{k-1}{2}$ then subtract the rest to get $$\frac{k-1}{2}\cdot x_1\cdot n_1+\frac{k-1}{2}\cdot x_2\cdot n_2+\frac{k-1}{2}\cdot x_3\cdot n_3+\sum_{i=r}^k (-x_i)\cdot n_i=1 \implies gcd(n_1,n_2...,n_k)=1$$

Answer 2

You are making this way too complicated.

There exists integers $x_1,x_2$ such that $n_1x_1+n_2x_2=1$. Letting $x_3=x_4=\cdots=x_k=0$. Then $\sum_{i=1}^{k} n_ix_i=1$ so the $x_i$ must be relatively prime.

Basically, $\gcd(x_1,x_2,\dots,x_k)\mid\gcd(x_1,x_2)$.

Answer 3

The condition $\forall i \ne j \in \{1,2 \ldots, k \}, \gcd (n_i,n_j)=1$ is too strong. Only two $i \ne j$ so $\gcd(n_i,n_j)=1$ is enough to imply $\gcd (n_1, \ldots, n_k)=1$.

Indeed, let $d=\gcd (n_1, \ldots, n_k)$ then $d \mid n_i, d \mid n_j$ so $d \mid \gcd (n_i,n_j)=1$ so $d=1$. Thus, $\gcd (n_1, \ldots, n_k)=1$.