Listing all coprimes 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)$
Unlike in this question, I don't want to prove it, but I have a simple question: Wikipedia claims that the ternary trees lists all the pairs. However, where are many pairs?! For example, 5 and 101 are coprime. How can we generate them? Can we?
I simply want a fast way to generate all coprime numbers to all numbers. Meaning that I want to create a Map that for every integer in 1..n will point into a List with all its coprimes. So the number 5 will list 2, 3 and 4 and 101 will list many, including 5.
I wanted to do it by generating all the coprimes, but failed :( How can I?
 A: Let $f(m, n) := (m + 2n, n)$ and $g(m, n) := (2m + n, m)$. Then $f^9(g(f(3, 1))) = (101, 5)$.
Using the ternary tree does not seem to give a very efficient way to map the natural numbers to all coprime pairs. A better way would be either
function coprimes(g)
    return { n ϵ N : gcd(n, g) = 1 }

or
function coprimes(g)
    P = { p : p is a prime that divides g }
    return { 1, 2, ..., g } \ { kp : k ϵ N, p ϵ P }

Here I just listed the coprimes $c$ with $c < g$ to keep the list finite. Note that the list of coprimes is usually big, on the order or the size of the number.
Now you said you want to list every coprime for every number. I assume you mean every coprime in a range $[1, ..., n]$. What you can do is use the sieve of Eratosthenes to get the prime factors of each number in the range, then do
# returns the first integer multiple of p that is larger than g
function f(g, p)
    return ceil((g + 1) / p) * p

function coprimes(g)
    list = { }
    pairs = array{ (f(g, p), p) : p prime factor of g }
    sort pairs non-decreasingly on first value of tuple
    while pairs is not empty
        (n, p) = pairs[0]
        add n, ..., min(g - 1, n + p - 1) to list
        if n + p < g
            replace pairs[0] by (n + p, p) and resort pairs
        else
            remove pairs[0] from the array
     return

which is, I think, slightly more efficient than the methods above.
Edit: It is probably easier to just list the numbers that are not coprime.
A: There are $\phi(n)$ numbers in the range $1..n$ coprime to $n$, say $k_0 .. k_{\phi(n)-1}$ (where $\phi$ corresponds to Euler's totient function).
To obtain the other numbers coprime to $n$, simply add a positive multiple of $n$ to one of $k_0 .. k_{\phi(n)-1}$.
If $i = r + q\phi(n)$ with $0 \le r < \phi(n)$, then the $i$-th ($0$-based) number coprime to $n$ is $k_i = k_r + qn$.
