Generating all coprime pairs

Question

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs.

All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint complete ternary trees, one tree starting from $(2,1)$ (for even-odd and odd-even pairs), and the other tree starting from $(3,1)$ (for odd-odd pairs). The children of each vertex $(m,n)$ are generated as follows:

• Branch 1: $(2m - n, m)$
• Branch 2: $(2m + n, m)$
• Branch 3: $(m + 2n, n)$

This scheme is exhaustive and non-redundant with no invalid members.

The listed sources are inaccessible to me, so I'm trying to prove the result myself. Let:

• $B_i$ be the linear mapping described by branch $i$
• $T_1^{(0)} = \{(2, 1)\}$ and $T_2^{(0)} = \{(3, 1)\}$
• $T_i^{(l+1)} = \bigcup_{j=1}^3 \{B_j(m, n):(m, n)\in T_i^{(l)}\}$) for $i = 1, 2$
• $T_i = \bigcup_{l \ge 0} T_i^{(l)}$ for $i = 1, 2$
• $S = \{(m, n): m > n > 0 \text{ and }m \perp n\}$.

I want to prove:

1. $T_1 \cup T_2 \supseteq S$ (exhaustive)
2. $T_i^{(l)} \cap T_j^{(k)} \ne \varnothing \implies i = j\text{ and }l = k$ (non-redundant)
3. $T_1 \cup T_2 \subseteq S$ (no invalid members)

3 is easy. If $ad - bc = \pm 1$ then $\gcd(am + bn, cm + dn) = \gcd(m, n)$. Since $\det B_i = \pm 1$ for all $i$ (only $B_2$ has negative determinant), our twin trees contain only coprime pairs. Moreover, a direct computation shows that each $B_i(m, n)$ is a big-small pair provided that $(m, n)$ is. The hypothesis $m > n$ is required only for $B_1$: $2m - n = m + m - n > m + 0 = m$.

For 2, it's easy to see that $T_1 \cap T_2 = \varnothing$ because every pair $(m, n)$ in $T_1$ satisfies $m - n \equiv 1$ (mod 2) whereas every pair $(m, n)$ in $T_2$ satisfies $m - n \equiv 0$ (mod 2). Thus, if $T_i^{(l)} \cap T_j^{(k)} \ne \varnothing$, then $i = j$. How do I prove $l = k$? Is there a computation I could do on the coordinates of the point $(m, n)$ to determine its level? Are there useful bounds on the elements of $T_i^{(l)}$? I computed $$B_2^{-1}B_1(m, n) = (m, -n),\quad B_3^{-1}B_1(m, n) = (-n, m),$$ $$B_1^{-1}B_2(m, n) = (m, -n),\quad B_3^{-1}B_2(m, n) = (n, m),$$ $$B_1^{-1}B_3(m, n) = (n, -m),\quad B_2^{-1}B_3(m, n) = (n, m).$$ All of these resulting pairs are forbidden (i.e. not in $S$). Does it follow that if $p$ = $B_i(q) = B_j(r)$, with $p, q, r$ pairs in the tree, then $i = j$ because $B_j^{-1}B_i(q)$ cannot be in the tree otherwise?

As for 1, I've not gone very far. Suppose $m > n > 0$ are coprime. There are five cases for $m$'s placement on the number line according to multiples of $n$:

1. $n < m < 2n$
2. $2n = m$
3. $2n < m < 3n$
4. $3n = m$
5. $3n < m$

Cases 2 and 4 are trivial to deal with. Case 1's points are precisely those which satisfy $B_1^{-1}(m, n) \in S$; case 3's, those such that $B_2^{-1}(m, n) \in S$; and case 5's, $B_3^{-1}(m, n)$. From here, I'm lost.

Any insights would be greatly appreciated. I'm also wondering, where did these three linear maps come from? If I wanted to generate coprime triples, could I do something similar? Is there some deeper, more general scheme underlying this construction?

Answer 1

I think these should be pretty easy to prove once you've shown that every coprime pair has a uniquely determined predecessor:

$$\text{branch 1:} \; (m',n') = (2m-n,m) \rightarrow (m,n) = (n',2n'-m')$$ $$\text{branch 2:} \; (m',n') = (2m+n,m) \rightarrow (m,n) = (n',m'-2n')$$ $$\text{branch 3:} \; (m',n') = (m+2n,n) \rightarrow (m,n) = (m'-2n',n')$$

You can see in all three cases you get one number of magnitude $2n'-m'$ and one equal to $n'$. Since m must be greater than n and both must be positive, at most one of these branch inverse operations will create a valid pair.

Both the forward and backward operations preserve $GCD(m,n)=1$. So as long as they are coprime, they will remain coprime up until $2n'=m'$ or $2n'=m'$ as these will give a zero or make m and n equal. Fortunately, these correspond to your starting states.

After re-reading your post it looks like your already basically figured out that there was a unique $B^{-1}$. From there you just need to show that it would also be co-prime (with the exceptions of the initial conditions), and that the sum of m,n must be strictly decreasing every time you apply $B^{-1}$. That lets you show that every co-prime can get back to one of your seeds, through exactly one path, thus if you reverse each path you can get from one of your seeds to every co-prime (in one way).