Tree of primitive Pythagorean triples

In mathematics, a tree of primitive Pythagorean triples is a data tree in which each node branches to three subsequent nodes with the infinite set of all nodes giving all (and only) primitive Pythagorean triples without duplication. In mathematics, a tree of primitive Pythagorean triples is a data tree in which each node branches to three subsequent nodes with the infinite set of all nodes giving all (and only) primitive Pythagorean triples without duplication. A Pythagorean triple is a set of three positive integers a, b, and c having the property that they can be respectively the two legs and the hypotenuse of a right triangle, thus satisfying the equation a 2 + b 2 = c 2 {displaystyle a^{2}+b^{2}=c^{2}} ; the triple is said to be primitive if and only if a, b, and c share no common divisor. Note that this implies that a, b, and c are also pairwise coprime. The set of all primitive Pythagorean triples has the structure of a rooted tree, specifically a ternary tree, in a natural way. This was first discovered by B. Berggren in 1934. F. J. M. Barning showed that when any of the three matrices is multiplied on the right by a column vector whose components form a Pythagorean triple, then the result is another column vector whose components are a different Pythagorean triple. If the initial triple is primitive, then so is the one that results. Thus each primitive Pythagorean triple has three 'children'. All primitive Pythagorean triples are descended in this way from the triple (3, 4, 5), and no primitive triple appears more than once. The result may be graphically represented as an infinite ternary tree with (3, 4, 5) at the root node (see classic tree at right). This tree also appeared in papers of A. Hall in 1970 and A. R. Kanga in 1990. It can be shown inductively that the tree contains primitive Pythagorean triples and nothing else by showing that starting from a primitive Pythagorean triple, such as is present at the initial node with (3, 4, 5), each generated triple is both Pythagorean and primitive. If any of the above matrices, say A, is applied to a triple (a, b, c)T having the Pythagorean property a2+b2=c2 to obtain a new triple (d, e, f)T = A(a, b, c)T, this new triple is also Pythagorean. This can be seen by writing out each of d, e, and f as the sum of three terms in a, b, and c, squaring each of them, and substituting c2=a2+b2 to obtain f2=d2+e2. This holds for B and C as well as for A. The matrices A, B, and C are all unimodular—that is, they have only integer entries and their determinants are ±1. Thus their inverses are also unimodular and in particular have only integer entries. So if any one of them, for example A, is applied to a primitive Pythagorean triple (a, b, c)T to obtain another triple (d, e, f)T, we have (d, e, f)T = A(a, b, c)T and hence (a, b, c)T = A−1(d, e, f)T. If any prime factor were shared by any two of (and hence all three of) d, e, and f then by this last equation that prime would also divide each of a, b, and c. So if a, b, and c are in fact pairwise coprime, then d, e, and f must be pairwise coprime as well. This holds for B and C as well as for A. To show that the tree contains every primitive Pythagorean triple, but no more than once, it suffices to show that for any such triple there is exactly one path back through the tree to the starting node (3, 4, 5). This can be seen by applying in turn each of the unimodular inverse matrices A−1, B−1, and C−1 to an arbitrary primitive Pythagorean triple (d, e, f), noting that by the above reasoning primitivity and the Pythagorean property are retained, and noting that for any triple larger than (3, 4, 5) exactly one of the inverse transition matrices yields a new triple with all positive entries (and a smaller hypotenuse). By induction, this new valid triple itself leads to exactly one smaller valid triple, and so forth. By the finiteness of the number of smaller and smaller potential hypotenuses, eventually (3, 4, 5) is reached. This proves that (d, e, f) does in fact occur in the tree, since it can be reached from (3, 4, 5) by reversing the steps; and it occurs uniquely because there was only one path from (d, e, f) to (3, 4, 5). The transformation using matrix A, if performed repeatedly from (a, b, c) = (3, 4, 5), preserves the feature b + 1 = c; matrix B preserves a – b = ±1 starting from (3, 4, 5); and matrix C preserves the feature a + 2 = c starting from (3, 4, 5).