A Euclidean algorithm problem 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?
 A: 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$.
A: 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..
