Número de factores relativamente primos

Question

Dado un número $n$ ¿de cuántas maneras puedes elegir dos factores que sean relativamente primos entre sí (es decir, que su máximo común divisor sea 1)?

Además, ¿voy en la dirección correcta al decir que si $n$ se escribe como $p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$ donde $p_i$ es un primo y $a_i\geq 1$ entonces el número de factores $n$ tiene es $(a_1 + 1)(a_2 + 1)\dots (a_k + 1)$ y cuando elijo un factor $x = p_1^{b_1}p_2^{b_2}\dots p_k^{b_k}$ el número de factores es $(c_1 + 1)(c_2 + 1)\dots (c_k + 1)$ donde $c_i = 0$ si $b_i\neq 0$ y $c_i = a_i$ ¿O no?

Answer 1

Interpretamos que la pregunta se refiere al número de pares desordenados de divisores (distintos) de $n$ que son relativamente primos. Para mí es más fácil pensar en términos de pares ordenados.

Así que estamos produciendo un par ordenado $(x,y)$ de divisores relativamente primos de $n$ . Examinar uno tras otro los primos $p_i$ . En cada prime tenemos tres tipos de opciones: (i) asignar $p_i$ à $x$ (ii) asignarlo a $y$ (iii) no asignarlo a ninguno de los dos. Si asignamos $p_i$ à $x$ se puede hacer en $a_i$ formas, para la potencia de $p_i$ está a nuestra disposición. Lo mismo ocurre con $y$ . Y no podemos asignar a ninguno de los dos en $1$ para un total de $2a_i+1$ . Por tanto, el número total de pares ordenados es $P$ donde $$P=\prod_1^k(2a_i+1).$$ Esto incluye el par ordenado $(1,1)$ . Ahora, para pares no ordenados de distintos divisores relativamente primos, hay $\frac{P-1}{2}$ posibilidades.

Observación: Si queremos que el producto de los dos factores sea $n$ el recuento resulta mucho más sencillo. Para los pares ordenados, elegimos un subconjunto del conjunto de los primos, y asignar $p_i^{a_i}$ en el subconjunto elegido a $x$ y asignar el resto a $y$ . Existen $2^k$ maneras de elegir $x$ y luego $y$ está determinada. Así que hay $2^k$ pares ordenados, y para $n\gt 1$ hay $2^{k-1}$ pares desordenados.

Answer 2

Separarlo en varios primos distintos es la dirección correcta; a partir de ahí te has desviado. Aunque podrías intentar generar o contar todos los pares de factores de $n$ no te va a servir de nada: hay una forma de generar los pares de factores relativamente primos que no implica comprobar si son realmente relativamente primos.

CONSEJO Si dos números $a,b$ son relativamente primos entre sí, ¿qué se puede decir sobre la presencia de un primo $p$ ¿Qué le dice esto sobre los pares de factores relativamente primos de un número dado? $n$ ?