# What is the number of elements in the set {(x,y): x|n, y|n, gcd(x,y)=1} ?.

Sloane's OEIS A048691 gives an explicit formula:(2*e(1)+1)*(2*e(2)+1)***(2*e(r)+1) where the e(i)'s are the exponents in the prime factorization of n.

It turns out that the same formula counts the number of divisors of n^2, and also the number of elements in the set {(a,b): lcm(a,b)=n}. I understand the derivation of the formula for these two sets but I do not know why the formula counts the number of elements in the set given above in the title.

Here is a paper that explains the formula for |{(a,b): lcm(a,b)=n}|. O. Bagdasar, On some functions involving the lcm and gcd of integer tuples, Scientific Publications of the State University of Novi Pazar, Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91--100.

Let $f(n)$ be the counting function for our set. We first show that $f$ is multiplicative. So we need to show that $f(ab)=f(a)f(b)$ whenever $\gcd(a,b)=1$.
Let $(x,y)$ be any ordered pair such that $x\mid a$, $y\mid b$, and $\gcd(x,y)=1$. Then $x$ has a unique representation as $x_ax_b$, where $x_a\mid a$ and $x_b\mid b$. Similarly, $y$ has a unique representation as $y_ay_b$. Note that $\gcd(x_a,y_a)=\gcd(x_b,y_b)=1$.
The mapping that takes $(x,y)$ to the ordered pair of pairs $((x_a,y_a), (x_b,y_b))$ is bijective, and $f(ab)=f(a)f(b)$ follows.
To finish, we need to compute $f(p^e)$ where $p$ is prime. The qualifying ordered pairs are all pairs $(1,p^t)$ and $(p^t,1)$, where $0\le t\le e$. There are $2e+1$ such pairs.
• The decomposition argument does generalize. Note that this is also the number of divisors of $n^k$, so that relationship remains. Something that would improve my answer is (say for the $k=2$ case, or in general) is to give a "natural" explicit bijection between the set of ordered pairs of our problem and the set of divisors of $n^2$. – André Nicolas Jan 11 '15 at 17:43