cuestión relativa a la función totient de Euler
Acabo de encontrarme con una pregunta en teoría de números que se relaciona con la función totiente de Euler. La pregunta es la siguiente:
Tenemos un entero positivo $n>1$. Encuentra la suma de todos los números$x$, tal que $x\in {1, 2, ..., n}$, que son primos relativos con n.
Lo resolví de la siguiente manera: Tenemos número $d$ que es relativamente primo con $n$, también tenemos eso $n-d$ es relativamente primo con $n$. Entonces, la suma total es$\frac{n*\phi(n)}{2}$
Sin embargo, sé que existe una solución con el uso del principio de exclusión de inclusión. ¿Podría explicarme cómo podría resolverlo usando PIE?
Respuestas
En general me gusta más tu solución, pero aquí vamos. Recordar que$[n]=\{1,2,\cdots, n\}.$ Considerar $n=p_1^{\alpha _1}\cdots p_k^{\alpha _k}$ llamada $A_r=\{x\in [n]:p_r|x\}$ y llama $s(A)=\sum _{a\in A}a$ luego por el PIE usando un peso (principalmente $s:[n]\longrightarrow \mathbb{R}$ definido antes) $$s([n])-\sum _{i = 1}^k(-1)^{i-1}\sum _{X\in \binom{[k]}{i}}s\left (\bigcap _{x\in X}A_x\right ).$$ Ahora, note que $s(A_j)=\sum _{p_j|d,d\leq n}d=p_j\sum _{i=1}^{n/p_j}i=p_j\binom{n/p_j+1}{2}=\frac{n}{2}(n/p_j+1).$ En general, puedes comprobar que $$s\left (\bigcap _{x\in X} A_x\right )=\prod _{x\in X} p_x \cdot \binom{n/(\prod _{x\in X} p_x)+1}{2}=\frac{n}{2}(n/(\prod _{x\in X} p_x)+1).$$ Conectando esto en la ecuación y notando que $s([n])$ se puede colocar dentro de la suma, obtienes $$\sum _{i = 0}^k(-1)^{i}\sum _{X\in \binom{[k]}{i}}s\left (\bigcap _{x\in X}A_x\right )=\frac{n}{2}\left (n+1+\sum _{i = 1}^k(-1)^{i}\sum _{X\in \binom{[k]}{i}}\left (n/(\prod _{x\in X} p_x)+1\right )\right )=\frac{n}{2}(n+1+n\prod _{x=1}^k (1-\frac{1}{p_x})+\sum _{i=1}^k(-1)^i\binom{k}{i})=\frac{n\cdot \varphi (n)}{2},$$ donde en el último paso usamos la definición de $\varphi$y el teorema del binomio.
Editar: Para aclarar, primero recuerde que el principio de exclusión de inclusión significa poner todo, luego quitar las repeticiones, luego agregar lo que quitó en la repetición, etc. Entonces, el$A_x$ van a ser los números que desea excluir, porque si $a\in A_x$ luego $a$ y $n$no son coprime. Ahora, en la teoría general del PIE, puede usar pesos (puede pensar en ello como en el sentido de probabilidad, la probabilidad es un tipo muy especial de peso de un conjunto). En este caso, nuestro peso es la suma de los elementos del conjunto. Si quieres leer más sobre esto, te remito al teorema 8.1 aquí o al Capítulo de PIE en el libro: "Un curso de enumeración" por M. Aigner.
Ahora, tenemos que calcular, así que primero recuerda que$1+2+\cdots +n=\frac{n(n+1)}{2}=\binom{n+1}{2}$ así que ves eso $\frac{n}{2}$Jugará un buen papel en la comprensión. Entonces calculamos$s(A_j)$ para juegos individuales $A_j$ notando que cada elemento es divisible por $p_j$ para que podamos pensar en un número como $p_j\cdot i$ para $i$ menor o igual a $n/p_j.$Cuando comprenda esto, puede intentar calcularlo para el conjunto general. Entonces el$\bigcap _x{\in X}A_x$ solo significa el conjunto de elementos divisibles por cada primo indexado por el conjunto $X$ por lo que cada elemento será un producto de esos números primos por un número menor que $\frac{n}{\text{multiplication of those primes}}.$ Cuando pones todo junto, notas que al factorizar $\frac{n}{2}$ obtienes el pastel habitual para la informática $\varphi$vea, por ejemplo, las respuestas aquí.