Let $a,b,c,d\in \mathbb{Z}$ and suppose we have the equation $ac+bd=1$. One way of thinking about this equation is it expresses the fact $\gcd(b,d)=1$. It is well-known that all other similar equations expressing that fact are of the form $(a+td)c+(b-tc)d=1$ for some $t\in\mathbb{Z}$.

Letting $a'=a+td,b'=b-tc$, one may ask if there is a "best" choice for $t$; or equivalently, if there is a best choice for $a',b'$. In some sense, the usual Euclidean algorithm (applied to $b,d$) gives a minimal linear combination--we'll call the resulting pair $(a',b')$ the Euclidean pair. But there are sometimes other situations where a different choice of $t$ is optimal. In any case, we can pass from $ac+bd=1$ to $a'c+b'd=1$.

Now, we can view this latter expression as a linear combination showing that $\gcd(a',b')=1$. So we can repeat the process to get a new $b',d'$ so that $a'b'+c'd'=1$. Continuing in this fashion by replacing either the $(a,c)$ pair or the $(b,d)$ pair with a new pair $(a',c')$ or $(b',d')$ respectively, then after a finite number of steps we can always reach the equation $1\cdot 1+ 0\cdot 0=1$. (One way to do this is just use the Euclidean pair for each replacement, except possibly at the end when one may need to pass from $0\cdot 0+1\cdot 1=1\mapsto 1\cdot 1+0\cdot 0=1$.)

My question is: Starting with any quadruple of integers $a,b,c,d\in\mathbb{Z}$ with $ac+bd=1$, is there an absolute bound $n\gg 0$ so that by performing some sequence of back-and-forth switching as described above we get to $1\cdot 1+0\cdot 0=1$ within at most $n$ steps?

The greedy algorithm of simply choosing the Euclidean pair will not give an absolute bound $n$, since we can easily construct a sequence which requires an arbitrarily large number of steps this way. But using the Euclidean pair is not always the best choice.

By the way, this number theory question originally arose in my study of perspective decompositions of the abelian group $\mathbb{Z}\oplus \mathbb{Z}$. The connection comes from associating nontrivial idempotents $E\in \mathbb{M}_2(\mathbb{Z})$ with 4-tuples $(a,b,c,d)$ satisfying $ac+bd=1$, by writing $E=\begin{pmatrix}ac & bc\\ ad & bd\end{pmatrix}$. [Here, $a$ is the gcd of the first column, etc...]

Further, I have a very ad hoc way of showing that the question above has a negative answer if we replace $\mathbb{Z}$ with the ring $\mathbb{F}_2[x]$. In that case, one can show that using Euclidean pairs is optimal.

cLet $a,b,c,d\in \mathbb{Z}$ and suppose we have the equation $ac+bd=1$. One way of thinking about this equation is it expresses the fact $\gcd(c,d)=1$. It is well-known that all other similar equations expressing that fact are of the form $(a+td)c+(b-tc)d=1$ for some $t\in\mathbb{Z}$.

Letting $a'=a+td,b'=b-tc$, one may ask if there is a "best" choice for $t$; or equivalently, if there is a best choice for $a',b'$. In some sense, the usual Euclidean algorithm (applied to $b,d$) gives a minimal linear combination--we'll call the resulting pair $(a',b')$ the Euclidean pair. But there are sometimes other situations where a different choice of $t$ is optimal. In any case, we can pass from $ac+bd=1$ to $a'c+b'd=1$.

Now, we can view this latter expression as a linear combination showing that $\gcd(a',b')=1$. So we can repeat the process to get a new $b',d'$ so that $a'c'+b'd'=1$. Continuing in this fashion by replacing either the $(a,c)$ pair or the $(b,d)$ pair with a new pair $(a',c')$ or $(b',d')$ respectively, then after a finite number of steps we can always reach the equation $1\cdot 1+ 0\cdot 0=1$. (One way to do this is just use the Euclidean pair for each replacement, except possibly at the end when one may need to pass from $0\cdot 0+1\cdot 1=1\mapsto 1\cdot 1+0\cdot 0=1$.)

My question is: Starting with any quadruple of integers $a,b,c,d\in\mathbb{Z}$ with $ac+bd=1$, is there an absolute bound $n\gg 0$ so that by performing some sequence of back-and-forth switching as described above we get to $1\cdot 1+0\cdot 0=1$ within at most $n$ steps?

The greedy algorithm of simply choosing the Euclidean pair will not give an absolute bound $n$, since we can easily construct a sequence which requires an arbitrarily large number of steps this way. But using the Euclidean pair is not always the best choice.

By the way, this number theory question originally arose in my study of perspective decompositions of the abelian group $\mathbb{Z}\oplus \mathbb{Z}$. The connection comes from associating nontrivial idempotents $E\in \mathbb{M}_2(\mathbb{Z})$ with 4-tuples $(a,b,c,d)$ satisfying $ac+bd=1$, by writing $E=\begin{pmatrix}ac & bc\\ ad & bd\end{pmatrix}$. [Here, $a$ is the gcd of the first column, etc...]

Further, I have a very ad hoc way of showing that the question above has a negative answer if we replace $\mathbb{Z}$ with the ring $\mathbb{F}_2[x]$. In that case, one can show that using Euclidean pairs is optimal.