2
$\begingroup$

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?
$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – Will Jagy
    Nov 14, 2021 at 21:51
  • $\begingroup$ @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|)$. $\endgroup$
    – Alex C
    Nov 14, 2021 at 23:18
  • 1
    $\begingroup$ 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 $\endgroup$
    – Will Jagy
    Nov 15, 2021 at 0:02
  • $\begingroup$ $$ \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} $$ $\endgroup$
    – Will Jagy
    Nov 15, 2021 at 0:34
  • 1
    $\begingroup$ 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} $$ $\endgroup$
    – Will Jagy
    Nov 15, 2021 at 1:32

1 Answer 1

0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 14, 2021 at 23:06
  • $\begingroup$ $\frac{53}{41} = [1,3,2,2,2]$, $\frac{22}{17} = [1,3,2,2]$, $\frac{9}{7} = [1,3,2]$, etc. $\endgroup$
    – Alex C
    Nov 15, 2021 at 1:48
  • $\begingroup$ The remaining piece is the proof of minimality of the chain obtained this way. $\endgroup$
    – Alex C
    Nov 15, 2021 at 2:09
  • 1
    $\begingroup$ @AlexC induction on the length of the continued fraction. $\endgroup$
    – Will Jagy
    Nov 15, 2021 at 2:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .