When does $2$ arise when using the Euclidean algorithm to compute greatest common divisors?

Question

When using the standard Euclidean algorithm to compute the greatest common divisor of a pair of relatively prime positive integers, the integer $2$ sometimes arises and sometimes does not. For example, $2$ arises when computing $$\gcd(19,11)=\gcd(11,8)=\gcd(8,3)=\gcd(3,2)=\gcd(2,1)=1$$ but does not arise when computing $$\gcd(29,11)=\gcd(11,7)=\gcd(7,4)=\gcd(4,3)=\gcd(3,1)=1.$$ Is there a characterization of the pairs of integers for which $2$ arises when using the standard Euclidean algorithm to compute their greatest common divisor?

Added: As Emil Jeřábek points out below, this question is equivalent to asking which rational numbers have the property that their continued fraction representation ends in $2$.

Answer 1

Let me present a criterion that may or may not be more transparent than the definition.

If $a,b\ge0$ are coprime, let $b^{-1}\bmod a$ denote the least $u\ge0$ such that $ub\equiv1\pmod a$. (I.e., $b^{-1}\bmod a\in\{0,\dots,a-1\}$ if $a>0$, and $1^{-1}\bmod0=1$, though the latter value will not really matter).

Proposition. Let $a,b\ge0$ be coprime. The Euclidean algorithm computing $\gcd(a,b)$ will encounter $2$ if and only if either $(a,b)=(1,2)$ or $$\frac a3<b^{-1}\bmod a\le\frac{2a}3.$$

To show this, let us first establish that the criterion is symmetric:

Lemma. Let $a,b\ge0$ be coprime, $\{a,b\}\ne\{1,2\}$. Then $$\frac a3<b^{-1}\bmod a\le\frac{2a}3\iff\frac b3<a^{-1}\bmod b\le\frac{2b}3.$$

Proof: The cases $a\le1$ or $b\le1$ can be checked easily, thus assume $a,b\ge2$. It suffices to prove the left-to-right implication. Put $u=b^{-1}\bmod a$ and $v=\bigl(b(a-u)+1\bigr)/a$, which is an integer such that $av\equiv1\pmod b$. Assume $a/3<u\le2a/3$; we will show $b/3<v\le2b/3$, which also implies $v=a^{-1}\bmod b$.

Since $3u\le2a$, we have $3av\ge3ab-2ab+3>ab$, thus $v>b/3$. Likewise, $3u\ge a+1$ gives $3av\le3ab-(a+1)b+3=2ab-b+3<2ab+a$, thus $v<(2b+1)/3$. Since $v$ is an integer, $v\le2b/3$. QED

Proof of the Proposition: We proceed by induction on the number of steps of the Euclidean algorithm. The cases $a\le2$ or $b\le1$ can be checked easily. If $a\ge3$ and $b\ge2$, the algorithm hits $2$ on input $(a,b)$ iff it hits $2$ on input $(b,a\bmod b)$, while the Lemma gives $$\begin{align*} \frac a3<b^{-1}\bmod a\le\frac{2a}3 &\iff\frac b3<a^{-1}\bmod b\le\frac{2b}3\\ &\iff\frac b3<(a\bmod b)^{-1}\bmod b\le\frac{2b}3. \end{align*}$$ Thus, it suffices to apply the induction hypothesis. QED

Answer 2

Building on Emil Jeřábek's answer, the whole reversed continued fraction expansion of a rational number $b/d$ can be obtained from the inverse of $b$ modulo $d$, as the continued fraction expansion of whichever of $b^{-1} \bmod d/d$ or $(d-b^{-1}\bmod d)/d$ is smaller (except that if the reversed continued fraction expansion ends in a $1$, this is then added to the second-to-last entry). In particular, this shows that to find the end of the continued fraction expansion it usually suffices to know the approximate value of the inverse of $b$. By the equivalence between continued fractions and the Euclidean algorithm, we can determine the last few steps of the Euclidean algortithm if we know the distribution of the inverse of $c$ modulo $d$.

The continued fraction $[a_0; a_1,\dots, a_n]$ defines the rational number obtained by starting with $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ and then applying the matrix $M= U^{a_0} R U^{a_1} R \dots RU^{a_n}$ where $U = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and $R = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, and dividing the first entry by the second. So in other words if we write $M = \begin{pmatrix} a & b \\ c& d \end{pmatrix}$ then the relevant rational number is $b/d$.

The transpose matrix is $M^T = V^{a_n} R V^{a_{n-1}} R \dots R V^{a_0}$ where $V = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$ and then since $ R V R^{-1} =U$ and $R^{-1}=R$, conjugating by $R$ gives

$$M^T = R U^{a_n} R U^{a_{n-1}} R \dots R U^{a_0} R .$$

Applying this to $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$, producing the rational number $c/d$, gives the number with continued fraction $[0;a_n,a_{n-1} ,\dots, a_1 ]$ since the $U^{a_0}$ term does not affect the vector.

Since $M$ has determinant $\pm 1$, $ bc \equiv \pm 1 \mod d$, i.e. $c$ is plus or minus the inverse of $b$ modulo $d$. Since $a_n \geq 2$, the continued fraction expansion of $c/d$ starts with $[0;2]$ so $c/d$ lies between $0$ and $1/2$, and thus $c$ is whichever of $b \bmod d$ or $d- b\bmod d$ is smaller.

However, if $a_1=1$ then this continued fraction expansion is not in canonical form and we must delete that term and add $1$ to $a_2$ to obtain the continued fraction expansion of $c/d$. This does not affect our ability to determine the tail of the continued fraction expansion of $b/d$.

A strange application of this, combined with Weil's bounds for exponential sums, is that if we generate pairs of numbers in a weird way, such as $x^7+1, y$ for $x,y$ random between $0$ and $N$, and then apply the Euclidean algorithm, throwing out pairs that are not relatively prime, the distribution of the numbers we see in the last few steps will be the same as the distribution of if we generate pairs of numbers in a usual way. (This is just because $x^{-1} \bmod y/y$ is equidistributed in $\mathbb R/\mathbb Z$ by Weyl's criterion for equidistribution and the Weil bound for exponential sums.)

This argument was partially inspired by this stackexchange answer of Stephen James.

Answer 3

Here is a sense in which exactly half the rationals have a continued fraction with last partial quotient two:

A composition of a natural number $n$ is an expression of $n$ as a sum of positive integers, $n=c_1+c_2+\dotsb+c_r$, where order matters (e.g., $3+2$ and $2+3$ count as different compositions of five). The number of compositions of $n$ is known to be $2^{n-1}$, e.g., $$ 4=3+1=2+2=1+3=2+1+1=1+2+1=1+1+2=1+1+1+1 $$ are the $2^{4-1}=8$ compositions of $4$.

The number of compositions of $n$ ending in $1$ is $2^{n-2}$, since there is an obvious one-one correspondence between compositions of $n$ ending in $1$, and compositions of $n-1$. So, the number of compositions of $n$ not ending in $1$ is also $2^{n-2}$.

There is a natural (canonical?) one-one correspondence between compositions not ending in $1$ and rational numbers exceeding $1$; $c_1+c_2+\dotsb+c_r$ corresponds to the continued fraction $[c_1;c_2,\dotsc,c_r]$.

The continued fractions with last partial quotient two correspond to the compositions with last summand $2$. The compositions of $n$ with last summand $2$ are in one-one correspondence with the compositions of $n-2$, of which there are $2^{n-3}$, which is exactly half the number of compositions of $n$ not ending in $1$. So, if we list the rational numbers in order of increasing sum of partial quotients of their continued fractions, then half of them will have last partial quotient two.