A back and forth Euclidean algorithm over the integers--does it have bounded length? 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.
 A: We get an isomorphic problem by switching $c$ with $d$, and replacing $b$ with $-b$.  Then we are considering matrices $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ in $SL_2(\mathbb{Z})$.  Passage from $(a,b)$ to $(a',b')$ amounts to multiplication by a matrix $T^t = \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}$ for some $t \in \mathbb{Z}$, and switching between $(a,b)$ and $(c,d)$ is (up to sign) given by multiplication by $S = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$.  The question then amounts to whether there is a uniform bound on the length of words in $S$ and $T^t$ (as $t$ ranges over integers) describing elements of $SL_2(\mathbb{Z})$, and the answer is that such a bound does not exist.
One way to see this is by examining the geometry of Ford circles in the complex upper half-plane.  $T$ translates the half-plane by integers (preserving the cusp at infinity), and $S$ more or less takes cusps to their reciprocals.  Thus, a composite of $S$ with $T^t$ takes the circle at infinity to a circle tangent to it.  A word describing an element $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ then necessarily has length at least as long as the chain of circles connecting the cusp at infinity with the cusp $a/c$, and such chains of circles have unbounded length (indeed, they have a sharp lower bound given by the length of signed continued fractions - the shortest word is the chain of circles touching the vertical line with real part $a/c$).
