1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Then generalizing, the number of k tuples (a(1),a(2),...,a(k)) such that each a(i)|n and each pair of a(i)'s is relatively prime would be: (ke(1)+1)*(ke(2)+1)***(k*e(r)+1) where the e(i)'s are the exponents in the prime factorization of n. Right? $\endgroup$ – Geoffrey Critzer Jan 11 '15 at 17:28
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Jan 11 '15 at 17:43
  • $\begingroup$ I have tried very hard over the last several weeks to establish such a bijection with no success. It would be a very welcome embellishment to the OEIS sequence mentioned above. $\endgroup$ – Geoffrey Critzer Jan 12 '15 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.