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 back and forth Euclidean algorithm over the integers--does it have bounded length?
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](http://en.wikipedia.org/wiki/Ford_circle) 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$).


