A Euclidean algorithm problem

Question

Suppose that, after running the Euclidean algorithm on two integers $a$ and $b$, we find that $r_n=3$, where $r_n$ is the last remainder in the Euclidean algorithm. Furthermore, we find that $r_{n-1}=6$ and $r_{n-2}=21$. What can we say about $a$ and $b$?

Obviously, by the definition of the Euclidean algorithm, $\gcd(a, b)=3$. However, that isn't sufficient (isn't strong enough for an iff condition). I tried for a long time to think of more conditionns, but only came up with a bunch of false conjectures. Can someone help me?

Answer 1

As described in this answer, we can apply the Extended Euclidean Algorithm to $21$ and $6$ as follows: $$ \begin{array}{r} &&\overset{\substack{\hspace{-1in}\left\lfloor\frac{21}6\right\rfloor\hspace{-1in}\\\downarrow\\[3pt]\,}}{3}&\overset{\substack{\hspace{-1in}\left\lfloor\frac63\right\rfloor\hspace{-1in}\\\downarrow\\[3pt]\,}}{2}\\\hline 0&1&-3&7\\ 1&0&1&-2\\ 21&6&3&0\\ \end{array} $$ Thus, the terminal three remainders, $(21,6,3)$, dictate and are dictated by the last two terms, $(3,2)$, in the continued fraction (along with the common factor of $3$). In fact, $(3;2)$ is the continued fraction for $\frac72=\frac{21}6$.

Answer 2

In the Euclidean algorithm, performed on the starting couple of positive integers $(n,m)$
the remainders follow the sequence $$ \eqalign{ & n = r_{\, - 2} = \left\lfloor {{n \over m}} \right\rfloor m + r_{\,0} \cr & m = r_{\, - 1} = \left\lfloor {{m \over {r_{\,0} }}} \right\rfloor r_{\,0} + r_{\,1} \cr & \vdots \cr & r_{\,k - 2} = \left\lfloor {{{r_{\,k - 2} } \over {r_{\,k - 1} }}} \right\rfloor r_{\,k - 1} + r_{\,k} \cr & \vdots \cr & r_{\,h - 4} = \left\lfloor {{{r_{\,h - 4} } \over {r_{\,h - 3} }}} \right\rfloor r_{\,h - 3} + r_{\,h - 2} \cr & r_{\,h - 3} = \left\lfloor {{{r_{\,h - 3} } \over {r_{\,h - 2} }}} \right\rfloor r_{\,h - 2} + r_{\,h - 1} \cr & r_{\,h - 2} = \left\lfloor {{{r_{\,h - 2} } \over {r_{\,h - 1} }}} \right\rfloor r_{\,h - 1} + \left( {0 = r_{\,h} } \right) \quad \left| {\;r_{\,h - 1} = \gcd (n,m) = g} \right. \cr} $$

where the sequence shall be strictly decreasing down to $0$ at step $h$, i.e. $$ 0 = r_{\,h} < \cdots < \,r_{\,k} \, < r_{\,k - 1} < \cdots < r_{\,0} \quad \left\{ {\matrix{ { \le \left| {\,n\,} \right|} & {\left| {\;0 = m} \right.} \cr { < \left| {\,m\,} \right|} & {\left| {\;0 \ne m} \right.} \cr } } \right. $$ That also implies that the $ r_k $ are all multiples of $g= \gcd(n,m)$

You are asking practically how the sequence can be reconstructed backwards. Let's start from the last line $$ \eqalign{ & s_{ - 2} = {{r_{\,h} } \over g} = 0 \cr & s_{ - 1} = {{r_{\,h - 1} } \over g} = 1 \cr & s_0 = {{r_{\,h - 2} } \over g} = \left\lfloor {{{r_{\,h - 2} } \over {r_{\,h - 1} }}} \right\rfloor = k_{\,0} = k_{\,0} s_{ - 1} + s_{ - 2} \cr & s_1 = {{r_{\,h - 3} } \over g} = \left\lfloor {{{r_{\,h - 3} } \over {r_{\,h - 2} }}} \right\rfloor {{r_{\,h - 2} } \over g} + {{r_{\,h - 1} } \over g} = k_{\,1} s_0 + s_{ - 1} \cr & s_2 = {{r_{\,h - 4} } \over g} = \left\lfloor {{{r_{\,h - 4} } \over {r_{\,h - 3} }}} \right\rfloor {{r_{\,h - 3} } \over g} + {{r_{\,h - 2} } \over g} = k_{\,2} s_1 + s_0 \cr & \quad \quad \vdots \cr & s_j = {{r_{\,h - j - 2} } \over g} = \left\lfloor {{{r_{\,h - j - 2} } \over {r_{\,h - j - 1} }}} \right\rfloor {{r_{\,h - j - 1} } \over g} + {{r_{\,h - j} } \over g} = k_{\,j} s_{j - 1} + s_{j - 2} \cr} $$ where the $ k_j$ are arbitrary integers greater than $1$.

In matrix form this recursion reads $$ \left( {\matrix{ {s_{n - 1} } \cr {s_n } \cr } } \right) = \left( {\matrix{ 0 & 1 \cr 1 & {k_n } \cr } } \right) \left( {\matrix{ {s_{n - 2} } \cr {s_{n - 1} } \cr } } \right) \quad \left| {\;\left( {\matrix{ {s_{ - 2} } \cr {s_{ - 1} } \cr } } \right) = \left( {\matrix{0 \cr 1 \cr } } \right)} \right. $$

In the example you give $$ \eqalign{ & g = 3, \cr & s_{ - 1} = {{r_{\,h - 1} } \over g} = {g \over g} = 1,\quad \cr & s_0 = {{r_{\,h - 2} } \over g} = {6 \over g} = 2 = k_0 ,\; \cr & s_1 = {{21} \over g} = \left\lfloor {{{r_{\,h - 3} } \over {r_{\,h - 2} }}} \right\rfloor {{r_{\,h - 2} } \over g} + {{r_{\,h - 1} } \over g} = \cr & = \left\lfloor {{{21} \over 6}} \right\rfloor {6 \over g} + {g \over g} = 3s_0 + s_{ - 1} = 7 \cr} $$ then $$ \eqalign{ & \left( {\matrix{ {s_{ - 1} } \cr {s_0 } \cr } } \right) = \left( {\matrix{ 0 & 1 \cr 1 & {k_0 } \cr } } \right)\left( {\matrix{ 0 \cr 1 \cr } } \right) = \left( {\matrix{ 0 & 1 \cr 1 & 2 \cr } } \right)\left( {\matrix{ 0 \cr 1 \cr } } \right) = \left( {\matrix{ 1 \cr 2 \cr } } \right) \cr & \left( {\matrix{ {s_0 } \cr {s_1 } \cr } } \right) = \left( {\matrix{ 0 & 1 \cr 1 & {k_1 } \cr } } \right)\left( {\matrix{ 1 \cr 2 \cr } } \right) = \left( {\matrix{ 0 & 1 \cr 1 & 3 \cr } } \right)\left( {\matrix{ 1 \cr 2 \cr } } \right) = \left( {\matrix{ 2 \cr 7 \cr } } \right) \cr} $$ and from here we can proceed with multiplying by the matrix, with any selected constant, e.g.: $$ \eqalign{ & \left( {\matrix{ 0 & 1 \cr 1 & 1 \cr } } \right) \left( {\matrix{ 2 \cr 7 \cr } } \right) = \left( {\matrix{ 7 \cr 9 \cr } } \right) \cr & \left( {\matrix{ 0 & 1 \cr 1 & 2 \cr } } \right) \left( {\matrix{ 2 \cr 7 \cr } } \right) = \left( {\matrix{ 7 \cr {16} \cr } } \right) \cr & \left( {\matrix{ 0 & 1 \cr 1 & 1 \cr } } \right)^{\,2} \left( {\matrix{ 2 \cr 7 \cr } } \right) = \left( {\matrix{ 9 \cr {16} \cr } } \right) \cr} $$ which correspond to the couples $(21,27), \,(21,48) , \, (27,48)$ already indicated by @robjohn.

In conclusion we have the general solution to the recursion as $$ \left( {\matrix{ {s_{n - 1} } \cr {s_n } \cr } } \right) = \prod\limits_{j = 0}^n {\left( {\matrix{ 0 & 1 \cr 1 & {k_j } \cr } } \right) \left( {\matrix{ 0 \cr 1 \cr } } \right)} $$ so that when the $k$'s are unitary we get the Fibonacci numbers, which are known to have the longest chain in the algorithm. But for general values of the constants, there is not a simple characterization of the numbers that can be obtained..