Let $n_1,n_2,\cdots n_k$ be $k$ natural numbers and $a_1,a_2,\cdots,a_k$ be integers such that $$gcd(n_1,n_2,\cdots,n_k)=a_1n_1+a_2n_2+\cdots+a_kn_k = \sum_{i=1}^{k}a_in_i$$ .GCD can always be expressed as a linear combination of $n_{i's}$(proof in comment), but my objective is to find natural numbers $n_i$ such that all of the $a_{i's}$ are non zero.

For $k=3$, $\text{gcd}(6,15,77)=6(102)+15(-51)+77(2) = 1$ will be a valid example, but $\text{gcd}(2,3,5)=2(-1)+3(1)+5(0)=1$ is not a valid example as $a_3=0$. Similarly, for $k=4$ , $\text{gcd}(6,15,35,77)=6*(46)+15(-23)+35(2)+77(0) = 1$ will not be a valid example as $a_4=0$, but $\text{gcd}(210,510,2805,10210)=210(-1518876)$ $+510(632865)$ $+2805(-1361)$ $+10210(2) = 5$ is a valid example. I was also able to find an example for $k=5$, $\text{gcd}(210,510,2805,10210,102102)$ $=210(93047862636)$$+510(-38769942765)$ $+2805(83376221)$$+10210(-122522)$$+102102(3) = 1$. I couldn't find an example for $k=6$.

I believe that for every natural number $k$, natural numbers $n_i$ exist which satisfy this property. But I am not able to find a proof or construct such numbers. For a particular $k$, let $(n_1,n_2,\cdots,n_k)$ and $(m_1,m_2,\cdots ,m_k)$ be two pairs satisfying this property. Define$(n_1,n_2,\cdots ,n_k) < (m_1,m_2,\cdots,m_k)$ if $\sum_{i=1}^{k} n_i < \sum_{i=1}^{k} m_i$ and they are equal if their sums are equal. Then for $k=2$ , $(2,3)$ is the smallest solution. For $k=3$ i believe it will be $(6,15,35)$, $\text{gcd}(6,15,35)=6(46)$$+15(-23)+35$$(2)=1$, but i don't have a proof for this. What will be the samllest solutions for other values of $k$?


Suppose Bezout is $\,d\, =\, 0\cdot n_1 +\, \cdots\, + 0\cdot n_j\, +\, a_{j+1}\, n_{j+1} + \cdots + a_k\, n_k,\, $ all $\,a_i \neq 0,\ j\ge 1$.

Choose $a_1\!\neq 0\,$ so $\,1 + a_1 n_1 + n_2 + \cdots + n_j =: c \ne 0.\ $ Multiply above Bezout equation by this

which yields that $\, d + d a_1 n_1\! + dn_2 + \cdots + dn_j =\, c a_{j+1}\, n_{j+1} + \cdots + c a_k\, n_k\,$ with all coef's $\neq 0$.

  • $\begingroup$ We can choose $\,a_1 = \pm1\,$ (if one choice yields $\,c = 0\,$ then the other choice yields $\,\mp 2n_1\neq 0)$ $\ \ $ $\endgroup$ Jan 26 '20 at 6:52

The standard Bézout's identity for $2$ integers, plus the Bézout's identity generalization to $3$ or more integers, confirms there exists integers $a_i, \; 1 \le i \le k$, such that

$$d=\gcd(n_1,n_2,\cdots,n_k)=\sum_{i=1}^{k}a_in_i \tag{1}\label{eq1A}$$

for any $k \ge 2$. First, consider the case where $k = 2$ to give

$$d = a_1 n_1 + a_2 n_2 \tag{2}\label{eq2A}$$

Both $a_1$ and $a_2$ cannot be $0$. Suppose one of them, WLOG $a_1$, is $0$. Then you can select new coefficients $a_1^{'} = a_1 + b\left(\frac{n_2}{d}\right)$ and $a_2^{'} = a_2 - b\left(\frac{n_1}{d}\right)$ for any integer $b$. For any $b \neq 0$ you have $a_1^{'} \neq 0$ and, for all but possibly $1$ value of $b$, you have $a_2^{'} \neq 0$, showing you can choose a $b$ to get $a_1^{'} \neq 0$ and $a_2^{'} \neq 0$.

I'm going to show by strong induction and construction you can always find for any $k \ge 2$ a set of all non-zero $a_i$ coefficients. The base case for $k = 2$ has been shown in the paragraph above. Assume it's true for all $k \le c$ for some integer $c \ge 2$. Consider $k = c + 1$. If all of the $a_i$ are non-zero, then you're done. Otherwise, since not all of the $a_i$ may be zero, you have some $e$, where $1 \le e \le c$, values of $a_i$ which are $0$.

Let $f_i$ for $1 \le i \le e$ be the indices of $a$ and $n$ where the coefficients are $0$. There are $2$ basic cases to consider.

Case 1:

If $e \ge 2$, then by the induction assumption there exists coefficients, call them $g_i ,\; 1 \le i \le e$, which are all are non-zero. Also, have $h$ be the $\gcd$ of the corresponding $n_i$ values. Note that $d \mid h$, say $h = md$ for some integer $m \ge 1$. Also, consider any integer $q \ge 2$. You then have

$$\sum_{i=1}^{e} (q)(g_i)(n_{f_i}) = q(h) = (qm)d \tag{3}\label{eq3A}$$

Now, consider \eqref{eq3A} minus $qm - 1$ times \eqref{eq1A}. The resulting value is $d$. Also, due to no overlap between the coefficients of the $2$ equations, all of the original zero coefficients are now the corresponding non-zero values of $(q)(g_i)$, plus the original non-zero coefficients are now the non-zero $-(qm-1)(a_i)$ values. Thus, all of the coefficients are now non-zero.

Case 2:

Consider $e = 1$. As before, have $f_1$ be the zero coefficient index. Choose any other coefficient and have $f_2$ be the index of that value. Use this to construct \eqref{eq3A} and proceed as before there. If the result has the other chosen coefficient to be non-zero, then you're done. Otherwise, increase $q$ by $1$, with this then causing the resulting coefficient to decrease by $m(a_i)$ and, thus, be non-zero. As before, the end result is a set of all non-zero coefficients.

Thus, coefficients can be chosen in all cases so it's true for $k = c + 1$ as well. This completes the induction procedure to show you can always choose non-zero coefficients.

Update: I later realized I could have started at $k = 1$, using a definition of $\gcd(n_1) = n_1$, to give that $a_1 = 1$ since $(1)n_1 = n_1$. This would have made the above induction proof shorter & simpler. Alternatively, I could have started as above but then, for Case 2, used just the one zero coefficient value with $h = n_1$ for use in the Case 1 procedure.


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.