Pares de números con un LCM dado

Question

¿Cómo podemos mostrar que el número de pares (donde$(a, b)$ es el mismo que$(b, a)$) con$LCM(a, b) = n$ es igual a:

$\frac{(2e_1+1)(2e_2+1)...(2e_k+1)+1}{2}$

Dónde

$n=p_1^{e_1}\cdot p_2^{e_2}\cdot ...\cdot p_k^{e_k}, p_i\space prime\space \forall 1\leq i\leq k$

Me las arreglé para adivinar esta fórmula para un problema de programación en el que estaba trabajando, pero estaría interesado en una deducción o prueba.

Answer 1

Primero cuente los pares con$\gcd(a,b)=n$ contando$(a,b)$ y$(b,a)$ como distintos. Tienes$a=\prod p_i^{r_i}$ y$b=\prod p_i^{s_i}$ y necesitas$\max(r_i,s_i)=e_i$ para todos$i$. Entonces, dado un entero positivo$e$, ¿cuántos pares$(r,s)$ de enteros no negativos hay con$\max(r,s)=e$?