questão relativa à função totiente de Euler
Acabei de me deparar com uma questão na teoria dos números que se relaciona com a função totiente de Euler. A questão é a seguinte:
Temos um número inteiro positivo $n>1$. Encontre a soma de todos os números$x$, de tal modo que $x\in {1, 2, ..., n}$, que são relativamente primos com n.
Resolvi isso da seguinte maneira: Temos número $d$ que é relativamente principal com $n$, nós também temos isso $n-d$ é relativamente primo com $n$. Portanto, a adição total é$\frac{n*\phi(n)}{2}$
No entanto, sei que existe uma solução com o uso do princípio de exclusão de inclusão. Você poderia me explicar como eu poderia resolver isso usando o PIE?
Respostas
Em geral, gosto mais da sua solução, mas vamos lá. Lembre-se disso$[n]=\{1,2,\cdots, n\}.$ Considerar $n=p_1^{\alpha _1}\cdots p_k^{\alpha _k}$ ligar $A_r=\{x\in [n]:p_r|x\}$ e ligar $s(A)=\sum _{a\in A}a$ então pelo PIE usando um 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 ).$$ Agora, observe 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).$ Em geral, você pode verificar se $$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).$$ Conectar isso na equação e perceber que $s([n])$ pode ser colocado dentro da soma, você obtém $$\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},$$ onde na última etapa usamos a definição de $\varphi$e o teorema binomial.
Edit: Para esclarecimento, primeiro lembre-se de que o princípio de exclusão de inclusão significa colocar tudo, em seguida, retire as repetições, em seguida, adicione o que você tirou na repetição, etc.$A_x$ vão ser os números que você deseja excluir, porque se $a\in A_x$ então $a$ e $n$não são coprime. Agora, na teoria geral do PIE, você pode usar pesos (você pode pensar nisso como no sentido de probabilidade, probabilidade é um tipo muito especial de peso de um conjunto). Nesse caso, nosso peso é a soma dos elementos do conjunto. Se você quiser ler mais sobre isto, eu me refiro a você ao teorema 8.1 aqui ou ao Capítulo de TORTA no livro: "Um curso em enumeração" por M. Aigner.
Agora, temos que calcular, então primeiro lembre-se de que$1+2+\cdots +n=\frac{n(n+1)}{2}=\binom{n+1}{2}$ então você meio que vê isso $\frac{n}{2}$vai desempenhar um bom papel no entendimento. Então calculamos$s(A_j)$ para conjuntos individuais $A_j$ percebendo que cada elemento é divisível por $p_j$ então podemos pensar em um número lá como $p_j\cdot i$ para $i$ menor ou igual a $n/p_j.$Quando você entende isso, pode tentar computá-lo para um conjunto geral. Então o$\bigcap _x{\in X}A_x$ significa apenas o conjunto de elementos divisíveis por cada primo indexado pelo conjunto $X$ então cada elemento será um produto desses primos vezes um número menor que $\frac{n}{\text{multiplication of those primes}}.$ Quando você coloca tudo junto, você percebe que ao fatorar $\frac{n}{2}$ você obtém o PIE usual para computação $\varphi$veja por exemplo as respostas aqui.