# Expressing GCD as a linear combination where coefficients are non zero

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

• math.stackexchange.com/questions/718827/…
– Sam
Jan 17 '20 at 18:23
• I added an answer showing a very simple method. Jan 26 '20 at 6:35
• $n_i n_j - n_j n_i = 0$. Jan 26 '20 at 7:26

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

• We can choose $\,a_1 = \pm1\,$ (if one choice yields $\,c = 0\,$ then the other choice yields $\,\mp 2n_1\neq 0)$ $\ \$ 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.