# Rank of a pair of coprime integers

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?
• not sure what you want. In continued fractions, consecutive convergents are connected. Anyway, I wrote a gcd thing that replaces the usual "back-substitution" with the continued fraction for the ratio of the given positive integers Nov 14, 2021 at 21:51
• @WillJagy Could you explain the connection with continued fractions, please? I am struggling to prove that we can always obtain $(x, y)$ such that $max(|x|, |y|)$ < $min(|a|, |b|)$ or $max(|x|, |y|)$ < $max(|a|, |b|)$. Nov 14, 2021 at 23:18
• Alex, your first chain for (41,53) are just the convergents for $\frac{53}{41},$ in reverse order. I put that in an answer. Your second chain for (41,61) are the convergents for $\frac{61}{41}.$ I suggest that the string of convergents always gives your "rank" If you have some more examples you have worked, let me know and I will put in the c.f., you may compare Nov 15, 2021 at 0:02
• $$\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}$$ Nov 15, 2021 at 0:34
• your $\frac{22}{17}$ is the penultimate convergent for $\frac{53}{41}.$ Perhaps you are looking at the initial string of divisions: the fractions in the left column are of no importance, those being $\frac{41}{12}, \frac{12}{5}, \frac{5}{2}, \frac{2}{1}.$ Ignore them. Just look at $$\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}$$ Nov 15, 2021 at 1:32

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$$

• Your sequence does not agree with his, so you should explain how they are related. I see no answers above to any of his questions. Nov 14, 2021 at 23:06
• $\frac{53}{41} = [1,3,2,2,2]$, $\frac{22}{17} = [1,3,2,2]$, $\frac{9}{7} = [1,3,2]$, etc. Nov 15, 2021 at 1:48
• The remaining piece is the proof of minimality of the chain obtained this way. Nov 15, 2021 at 2:09
• @AlexC induction on the length of the continued fraction. Nov 15, 2021 at 2:14