Algebra question on transformation of an n-tuple to $a = (a_1, \dots , a_n)$ to $(1, 0, \dots ,0)$

Question

Let $n\geq 2$ be a natural number. An elementary transformation of an $n$-tuple, of integers $\mathbf{b} = (b_1, b_2, \dots , b_n)$, is a new $n$-tuple obtained from $\mathbf{b}$ by changing a combonent $b_i$ to $b_i +cb_j$ for some $j \neq i$ and $c \in \mathbb{Z}$. Let $a_1,\dots, a_n$ be integers such that $\gcd(a_1, \dots, a_n) = 1 $. Show that there is a sequence of elementary transformations, transforming the n-tuple $\mathbf{a} = (a_1, \dots, a_n)$ to the $n$-tuple $(1,0,\dots ,0)$.

I'm struggling with the how to construct a number $c \in \mathbb{Z}$ such that $b_i + cb_j = 1$.

How do you demonstrate, or construct such a number, then iterate to transform the $n$-tuple?

Answer 1

I'm struggling with the how to construct a number $c \in \mathbb{Z}$ such that $b_i + cb_j = 1$.

You have

$$b_i + cb_j = 1 \implies cb_j = 1 - b_i \implies b_j \mid 1 - b_i \tag{1}\label{eq1A}$$

Note you can have sets of integers where \eqref{eq1A} doesn't hold for any $i$ or $j$. Thus, this does not, at least directly, lead to the solution, so I don't see how to use Bezout's lemma, as suggested in the comments, for proving the general case.

Instead, start with the initial stated conditions, i.e., $n \ge 2$, the $a_i$ are integers, and

$$\gcd(a_1, \dots, a_n) = 1 \tag{2}\label{eq2A}$$

One complicating factor is if any of the $a_i$ are $0$. The Properties section of Wikipedia's "Greatest common divisor" article states in the third bullet point

$\gcd(a, 0) = |a|$, for $a \neq 0$, since any number is a divisor of 0, and the greatest divisor of $a$ is $|a|$.

This, I believe, is well accepted. However, if $a = 0$, then what is $\gcd(0, 0)$? This is not quite so well defined. Later in that same section, the fourth last bullet point starts with

It is sometimes useful to define $\gcd(0, 0) = 0$ and $\operatorname{lcm}(0, 0) = 0$ because ...

Also, Wolfram Alpha gives a result of $0$. However, Quora's What is the GCD of 0 and 0? has an answer by "Nicolas Daoust, Mathematics teacher" which states

It's undefined (not that it would be useful anyway).

I've seen other people also claim it's undefined, but regardless of it being $0$ or undefined, not all $a_i$ can be $0$ for \eqref{eq2A} to hold. If you have $n - 1$ values of $0$ instead, then the remaining value must be $1$ or $-1$. If it's the first value, if it's $-1$ you can make it $1$ with a $0$ value, and in either case you're done. Otherwise, if it's at $a_i, \; i \gt 1$, then for $a_i = 1$, use $b_1 = a_1 + a_i = 1$ and then $b_i = a_i - b_1$ (and similarly handle $a_i = -1$).

If there's $n - 2$ or fewer $0$ values, this means there's $2$ or more non-zero values. If any of them are $1$ or $-1$, then if it's $-1$ you can make it $1$ using another value. If this value of $1$ is not in the first spot already, you can make the first one $1$ using this value. After that, you can get all of the rest of the values to be $0$ using the first one.

Otherwise, among all the non-zero values, you have $|a_i| \gt 1$ for all $i$, so the coprime requirement means $|a_i| \neq |a_j|$ for all $i \neq j$. Thus, there's a unique maximum absolute value, call it's index $i$. Among the remaining smaller non-zero value(s), \eqref{eq2A} indicates at least one is relatively prime to $a_i$. Call this element's index $j$. The division algorithm states there's unique integers $q$ and $r$ such that

$$a_i = qa_j + r, \; 0 \le r \lt |a_j| \tag{3}\label{eq3A}$$

Note the coprime property means $r \neq 0$, plus $\gcd(r, a_j) = 1$. Choose $c = -q$ so you get $b_i = a_i - qa_j = r$. You now have the same conditions as before, but with $i$ and $j$ switched around. Thus, keep repeating the procedure to get new and smaller values of positive $r$ each time while switching $i$ and $j$ at each stage until, eventually, the $r$ will become $1$ (note for it become $0$ means either $b_i$ or $b_j$ was $1$ at the previous stage), so either $b_i$ or $b_j$ is then $1$ at that stage.

As before, you can then use this to make the first value $1$, if it's not already, and the rest of the values $0$.

Answer 2

You cannot necessarily make $1$ appear in a single step. There are several possible pitfalls:

• Any pair of entries may have non-trivial gcds. Consider the vector $(b_1,b_2,b_3)=(6,10,15)$. No matter what you do with $b_1$ and $b_2$ you end up with an even number. Similarly, an elementary operation only involving $b_1$ and $b_3$ can only give multiples of three, and operations with $b_2$ and $b_3$ alone yield multiples of five.
• A pair may be coprime, but needs more steps to reach the gcd. Not unlike Euclid's algorithm that, more often than not, needs more than a single iteration.

---

Instead you should work to recursively produce smaller and smaller non-zero absolute values:

1. Select an index $i_0$ such that $|b_{i_0}|$ is non-zero and as small as possible. If the absolute value is $1$, then we are done and can stop this process. Otherwise, continue.
2. For all other indices $i\neq i_0$ carry out a single step of the division algorithm, replacing $b_i$ with $r_i=b_i+q\cdot b_{i_0}$ such that $|r_i|<|b_{i_0}|$. Observe that $\gcd(r_1,\ldots,r_n,b_{i_0})=\gcd(b_1,b_2,\ldots,b_n)$.
3. If all the $r_i$s are zero, then $b_{i_0}$ was a common factor. Working under the assumptions that the gcd is equal to one and $|b_{i_0}|>1$, this is impossible. So there exists an index $j$ such that $0<|r_j|<|b_{i_0}|$. We made progress, and can continue from step 1.

Because you can decrease a positive integer only finitely many times before hitting $1$, the algorithm stops.

---

With the earlier example $(b_1,b_2,b_3)=(6,10,15)$ it would go as follows:

1. $b_1=6$ is the smallest component, so according to the rule in step 2 we transform $$(6,10,15)\mapsto (6,10-1\cdot6,15-2\cdot6)=(6,4,3).$$
2. In the next step $b_3=3$ is the smallest, so this time Step 2 calls for the transformation $$(6,4,3)\mapsto (6-2\cdot3,4-1\cdot3,3)=(0,1,3).$$ We got the desired $1$, and are content.

---

After you got that single $1$ to appear, another run of Step 2 makes the rest of them equal to zero.