Generating all coprime pairs 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: 


*

*$T_1 \cup T_2 \supseteq S$ (exhaustive)

*$T_i^{(l)} \cap T_j^{(k)} \ne \varnothing \implies i = j\text{ and }l = k$ (non-redundant)

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


*

*$n < m < 2n$

*$2n = m$

*$2n < m < 3n$

*$3n = m$

*$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?
 A: 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).
