WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

Generating All Coprime Pairs

generations

view

plot

tree

Two integers are said to be coprime (or relatively prime) if they do not share a common divisor different than 1. For instance, 4 and 9 are coprime (no common divisor except 1), but 12 and 15 are not (common divisor 3). The plot shows generations of coprime pairs

(m,n)

, starting from

(2,1)

and

(3,1)

, where three new pairs are produced at each step:

(2m-n,m)

(2m+n,m)

, and

(m+2n,n)

. The resulting triplets can be arranged in two complete ternary trees. The procedure described here generates all coprime pairs without repetition; the colors represent the different generations.

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.

I understand and wish to continue anyway »