Editing Coprime integers (section)

==Generating all coprime pairs==
[[File:Coprime8.svg|300px|thumb|The [[rooted tree|tree rooted]] at (2, 1). The root (2, 1) is marked red, its three children are shown in orange, third generation is yellow, and so on in the rainbow order.]]
All pairs of positive coprime numbers {{math|(''m'', ''n'')}} (with {{math|''m'' > ''n''}}) can be arranged in two disjoint complete [[ternary tree]]s, one tree starting from {{math|(2, 1)}} (for even–odd and odd–even pairs),<ref>{{Citation |last=Saunders |first=Robert |name-list-style=amp |last2=Randall |first2=Trevor |title=The family tree of the Pythagorean triplets revisited |journal=Mathematical Gazette |volume=78 |date=July 1994 |pages=190–193|doi=10.2307/3618576 }}.</ref> and the other tree starting from {{math|(3, 1)}} (for odd–odd pairs).<ref>{{Citation |last=Mitchell |first=Douglas W. |title=An alternative characterisation of all primitive Pythagorean triples |journal=Mathematical Gazette |volume=85 |date=July 2001 |pages= 273–275 |doi=10.2307/3622017}}.</ref> The children of each vertex {{math|(''m'', ''n'')}} are generated as follows:
*Branch 1: <math>(2m-n,m)</math>
*Branch 2: <math>(2m+n,m)</math>
*Branch 3: <math>(m+2n,n)</math>

This scheme is exhaustive and non-redundant with no invalid members. This can be proved by remarking that, if <math>(a,b)</math> is a coprime pair with <math>a>b,</math> then 
*if <math>a>3b,</math> then  <math>(a,b)</math> is a child of <math>(m,n)=(a-2b, b)</math> along branch 3;
*if <math>2b<a<3b,</math> then <math>(a,b)</math> is a child of <math>(m,n)=(b, a-2b)</math> along branch 2;
*if <math>b<a<2b,</math> then <math>(a,b)</math> is a child of <math>(m,n)=(b, 2b-a)</math> along branch 1.
In all cases <math>(m,n)</math> is a "smaller" coprime pair with <math>m>n.</math> This process of "computing the father" can stop only if either <math>a=2b</math> or <math>a=3b.</math> In these cases, coprimality, implies that the pair is either <math>(2,1)</math> or <math>(3,1).</math>

Another (much simpler) way to generate a tree of positive coprime pairs {{math|(''m'', ''n'')}} (with {{math|''m'' > ''n''}}) is by means of two generators <math>f:(m,n)\rightarrow(m+n,n)</math> and <math>g:(m,n)\rightarrow(m+n,m)</math>, starting with the root <math>(2,1)</math>. The resulting binary tree, the [[Calkin–Wilf tree]], is exhaustive and non-redundant, which can be seen as follows. Given a coprime pair one recursively applies <math>f^{-1}</math> or <math>g^{-1}</math> depending on which of them yields a positive coprime pair with {{math|''m'' > ''n''}}. Since only one does, the tree is non-redundant. Since by this procedure one is bound to arrive at the root, the tree is exhaustive.