$\sum\limits_{d \mid n} \mu(d) \omega(n/d)=0$ para los números compuestos. ¿Cómo?

Question

Necesito un poco de ayuda con la última(?) paso en una prueba y no estoy seguro de cómo debo proceder... $\mu(n)$ es la función de Möbius y $\omega(n)$ es el número de los distintos factores primos. Vemos que para $n$ prime, $$\sum_{d \mid n}\mu(d)\omega(n/d )=\mu(1)\omega(n)+\mu(n)\omega(1)=1.$$ Pero para $n$ compuesto estoy en una pérdida. Mi idea es de alguna forma demostrar que si $n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, entonces los términos de la siguiente suma que se anulan unas a otras, como esta: $$\sum_{d \mid n}\mu(d)\omega(n/d )=\omega(n)-\sum\omega\left(\frac{n}{p_i}\right)+\sum\omega\left(\frac{n}{p_ip_j}\right)+\ldots+\sum\omega\left(\frac{n}{p_1p_2\ldots p_k}\right)(-1)^{k},$$ donde nos acaba de saltar la divisores con exponente $a_i>1$ desde $\mu$ cancelaría. Hay una manera de lograr esto? O es esta tontería?



Añadido (aclaración):

Para $n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, $$\sum_{d \mid n}\mu(d)\omega \left( \frac{n}{d} \right)=\omega(n)+\underbrace{\mu(p_1) \omega(n/p_1)+ \ldots+\mu(p_k) \omega(n/p_k)}_{-\sum\omega\left(\frac{n}{p_i}\right)}+ \ldots + \mu(p_1 \ldots p_k) \omega\left(\frac{n}{p_1\ldots p_k}\right)$$ donde$\mu(p_i)=-1$$\mu(p_1 \ldots p_k)=(-1)^{k}$. Así que no suma de los términos con plaza de factores, puesto que serían 0, en cualquier caso.

Answer 1

Actualizado con pesados aclaraciones / elaboraciones.

Deje $f(n) = \sum_{d|n} \mu(d) \omega(n/d)$. Entonces, por Möbius inversión, tenemos $\omega(n) = \sum_{d|n} f(d)$. Deje $g(m)$ será la media aritmética de la función que evalúa a $1$ primer $m$ $0$ compuesto $m$. Entonces podemos escribir la diferencia de la función de $h(n) = \sum_{d|n} [f(d)-g(d)]=0$, y el uso de Möbius de la inversión de nuevo en la dirección inversa para obtener $f(n)-g(n)=\sum_{d|n} \mu(d) h(n/d) = 0$, lo que demuestra que la hipótesis original.

(Originalmente, yo creía que algún tipo de inducción se adapta mejor para terminar esta prueba, pero descubrió que no iba a funcionar mientras que la segunda inversión sería.)

---

Para ir de su posterior cancelación de la suma a la conclusión deseada, vamos a dividir $n$'s de la descomposición en factores primos en dos componentes, un "$\mu$" y un "$\mu$-gratis" en la parte, como $n=ab$ donde $a=q_1\cdots q_k$ $b= p_1^{e_1}\cdots p_l^{e_l}$ con exponentes $e_i\ge 2$. También escribo $b'=p_1\cdots p_l$. Para divisores $d|n$, escribimos $d=d_1d_2$ donde$d_1|a$$d_2|b$. A continuación, $\mu(d)\ne 0$ si y sólo si $d_2|b'$, así que podemos escribir como la suma

$$\sum_{d_1|a}\, \sum_{d_2|b'} \mu(d_1d_2) \omega\left(\frac{ab}{d_1d_2}\right) = \left(\sum_{d_1|a} \mu(d_1)[l +\omega(a/d_1)]\right)\left( \sum_{d_2|b'} \mu(d_2)\right)$$

(Tenga en cuenta que$\omega(b/d_2)=l$, independientemente de $d_2$ a causa de los exponentes en $b$'s de la descomposición en factores primos, y hacemos uso de las separaciones $\omega(xy) = \omega(x)+\omega(y)$, $\mu(xy)=\mu(x)\mu(y)$ al $\gcd(x,y)=1$.) El factor de la derecha de arriba es $0$, excepto cuando se $b'=1$, es decir, cuando se $n=a$. En ese caso se puede reducir aún más la suma de

$$\sum_{d_1|a} \mu(d_1)\omega(a/d_1).$$

Ahora mi original razonamiento patadas, dejando $Q$ el conjunto de factores primos de a $a$, y luego el siguiente explícita la deducción en user10676 respuesta.

Answer 2

Vamos $P_i(k)$, $i=1,2,...\binom{\omega(n)}{k}$, ser una enumeración de los productos de $k$ de los factores primos de a $n$, e $\nu(n)$ el número de factores primos de a $n$ con exponente $1$. A continuación, $\binom{\nu(n)}{j}$ es el número de formas de elegir los $j$ primos con exponente $1$, e $\binom{\omega(n)-\nu(n)}{k-j}$ es el número de formas de elegir los $k-j$ primos con exponente mayor que $1$. Los números primos con exponente $1$ $n$ aparecen en $P_i(k)$ disminuye el $\omega(\frac{n}{P_i(k)})$$\omega(n)-j$. Por lo tanto, $$ \begin{align} \sum_{i=1}^{\binom{\omega(n)}{k}}\omega(\frac{n}{P_i(k)}) &=\sum_{j=0}^k \binom{\nu(n)}{j}\binom{\omega(n)\!-\!\nu(n)}{k\!-\!j}(\omega(n)\!-\!j)\\ &=\binom{\omega(n)}{k}\omega(n)-\sum_{j=0}^k \;j\binom{\nu(n)}{j}\binom{\omega(n)\!-\!\nu(n)}{k\!-\!j}\\ &=\binom{\omega(n)}{k}\omega(n)-\sum_{j=1}^k \;\nu(n)\binom{\nu(n)\!-\!1}{j\!-\!1}\binom{\omega(n)\!-\!\nu(n)}{k\!-\!j}\\ &=\binom{\omega(n)}{k}\omega(n)-\binom{\omega(n)\!-\!1}{k\!-\!1}\nu(n) \end{align} $$ Debido a $\sum_k \binom{\omega(n)}{k}\;(-1)^k = 1$ al $\omega(n)=0$ $0$ otra manera, conseguimos que su alternando suma es $0$ al $\omega(n)=0$ $\nu(n)$ al $\omega(n)=1$ $0$ al $\omega(n)>1$.

$\omega(n)=0$ sólo cuando $n=1$. $\omega(n)=1$ y $\nu(n)=1$ sólo al $n$ es primo. Al $n$ es compuesto, $\omega(n)>1$ o $\nu(n)=0$. Este debe manejar todos los casos.

Answer 3

Aquí es un camino para terminar lo que han empezado, como se sugiere por Anon.

Deje $P$ el conjunto de los números primos factores de $n$. Entonces uno tiene $$ \sum_{d|n} \mu(d) \omega(n/d) = \sum_{I \subset P} (-1)^{|I|} (|P|-|I|) $$ Luego se divide la suma de acuerdo con el cardenal de $I$: $$ \sum_{d|n} \mu(d) \omega(n/d) = \sum_{k =0}^{|P|} \binom{|P|}{k} (-1)^{k} (|P|-k) $$ Concluir con los hechos que $$ \sum_{k=0}^{|P|} \binom{|P|}{k} (-1)^{k} = \begin{cases} 0, & \text{if } |P| \geq 1 \\ 1, & \text{if } |P|=0 \end{cases} $$ y $$ \sum_{k=0}^{|P|} \binom{|P|}{k} k (-1)^{k} = \begin{cases} 0, & \text{if } |P| \geq 2 \\ -1, & \text{if } |P|=1 \\ 0, & \text{if } |P|=0. \end{cases} $$ (Por último, observe que $k\binom{N}{k} = N\binom{N-1}{k-1}$)

Answer 4

Definir $k(n)$ $1$ si $n$ es el primer y $0$ si n es compuesto, entonces

$$\sum_{d\mid n}k(d)=\sum_{p\mid n}k(p)=\sum_{p\mid n}1=\omega(n)$$

Y por Möbius de la inversión de la fórmula,

$$k(n)=\sum_{d\mid n}\mu(d)\omega(\frac{n}{d})$$

Como se requiere