Rank of a pair of coprime integers

Question

Let's say two pairs of coprime integers $(a, b)$ and $(c, d)$ are connected if $ac + bd = 1$.

A connected chain, or just a chain, is a sequence of coprime pairs in which every two consecutive pairs are connected.

Clearly, if $(a, b)$ is connected to $(c, d)$, then $(a, b)$ is connected to $(c + nb, d - na)$ for an integer $n$.

Using the property, we may find a connected pair $(x, y)$ such that $max(|x|,|y|) < max(|a|,|b|)$.

Continuing the process we may build a chain that ends on $(0, 1)$ or $(1, 0)$ in absolute values.

Examples (in absolute values):

• $(41, 53)$, $(22, 17)$, $(7, 9)$, $(4, 3)$, $(1, 1)$, $(0, 1)$.
• $(41, 53)$, $(31, 24)$, $(7, 9)$, $(4, 3)$, $(1, 1)$, $(0, 1)$.

The described algorithm may give chains of different length:

• $(41, 61)$, $(58, 39)$, $(2, 3)$, $(1, 1)$, $(0, 1)$.
• $(41, 61)$, $(3, 2)$, $(1, 1)$, $(0, 1)$.

Let's define the rank of a pair of coprime integers $(a, b)$ as the minimal length within all possible chains connecting $(a, b)$ with $(0, 1)$ or $(1, 0)$ in absolute values.

Let's call a chain with the minimal length a minimal chain for $(a, b)$.

Questions:

1. Does the rank exist for any pair of coprime or prime integers?
2. Is there a maximal rank within all pairs of coprime or prime integers with rank?
3. Is there an algorithm of constructing a minimal chain or calculating the rank of a given coprime pair?

Answer 1

Your question (3), begin with your coprime pair $(a,b)$ with $a > b > 0,$ the minimal chain comes from using the Extended Euclidean Algorithm and writing the (simple) continued fraction for $\frac{a}{b},$ then let each convergent $\frac{p}{q}$ be part of the chain, as pair $(p,q)$

$$ \gcd( 53, 41 ) = ??? $$

$$ \frac{ 53 }{ 41 } = 1 + \frac{ 12 }{ 41 } $$ $$ \frac{ 41 }{ 12 } = 3 + \frac{ 5 }{ 12 } $$ $$ \frac{ 12 }{ 5 } = 2 + \frac{ 2 }{ 5 } $$ $$ \frac{ 5 }{ 2 } = 2 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 1 & & 3 & & 2 & & 2 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 4 }{ 3 } & & \frac{ 9 }{ 7 } & & \frac{ 22 }{ 17 } & & \frac{ 53 }{ 41 } \end{array} $$ $$ $$ $$ 53 \cdot 17 - 41 \cdot 22 = -1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \gcd( 61, 41 ) = ??? $$

$$ \frac{ 61 }{ 41 } = 1 + \frac{ 20 }{ 41 } $$ $$ \frac{ 41 }{ 20 } = 2 + \frac{ 1 }{ 20 } $$ $$ \frac{ 20 }{ 1 } = 20 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 1 & & 2 & & 20 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 61 }{ 41 } \end{array} $$ $$ $$ $$ 61 \cdot 2 - 41 \cdot 3 = -1 $$