$$\varphi(n)=n\prod_{p \ \text{prime}} (1-1/p)$$
¿Se puede derivar esta fórmula útil sin utilizar el hecho de que la función φ de Euler es multiplicativa?
Respuestas
¿Demasiados anuncios?
Bien, necesitas algo de propiedad. Escoger un número al azar de$1$$n$. Dado el primer divisor $p$$n$, ¿cuál es la probabilidad de que su elección al azar no es divisible por $p$? Es $1-\frac1p$. Entonces usted necesita para probar que estas probabilidades son independientes, es decir, si hemos de escoger un número al azar de $1$ $n$no divisible por $p_1,\dots,p_k$, entonces el (condicional) probabilidad de que no es divisible por algunos de los diferentes $p$ aún $1-\frac1p$.
En última instancia, esto muestra que la probabilidad de que un número aleatorio de $1$ $n$es relativamente primer a $n$ es:
$$\frac{\phi(n)}{n} = \prod_{p\mid n} \left(1-\frac1p\right)$$
Demostrando que la independencia es esencialmente el mismo como lo demuestra multiplicativo, pero tiene un sabor diferente.
Otro método es hacer una inclusión-exclusión en el argumento.
Moe Sisko
Puntos
3370
Que $n=\prod_{i=1}^{k}p_{i}^{a_i}$ donde el %#% de #% son números primos distintos y el %#% de #% son todos $p_i$. Que $a_i$ denotan el subconjunto de $\geq1$, todos cuyos elementos son divisibles por $A_i$. Entonces el conjunto de $\{1,2,\ldots, n\}$ es precisamente la Unión de la %#% de #% y tenemos, desde el principio de inclusión-exclusión,
$p_i$$
que nos da,
$A := \{m|1 \leq m \leq n, {\rm gcd}(m,n) \gt 1\}$$
Así, $A_i$ $ que nos da el resultado, $$|A|=\sum_i|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i\cap A_j \cap A_k|-\cdots$ $
justartem
Puntos
13
El teorema en sí es parcialmente sugerencias sobre la propiedad multiplicativa de $\varphi$ desde que se solicita por separado en los números primos.
No sé si el siguiente argumento es útil.
Deje $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}$, a continuación, un número de $a$ es coprime a $n$ si y sólo si $a$ es congruente a un número que no es múltiplo de $p_i\bmod p_i^{\alpha_i}$ por cada $i$. Desde el set $\{1,2,3\dots n\}$ es una completa residuo del sistema y por el teorema del resto chino no es exactamente una solución de $\bmod n$ a cada sistema de la forma:
$x\equiv a_1 \bmod p_1^{\alpha_1}$
$x\equiv a_2 \bmod p_2^{\alpha_2}$
....
$x\equiv a_r \bmod p_r^{\alpha_r}$
llegamos a la conclusión de la número de número relativamente primer a $n$ en el conjunto de $\{1,2,3\dots n\}$ es igual al número de formas en que lugar adecuado $a_i$'s a la conguence sistema anterior. Por supuesto, hay $p^{\alpha_i-1}(p-1)$ formas de hacerlo para cada una de las $a_i$. Por lo tanto, $\varphi(n)=\prod\limits_{i=1}^rp^{\alpha_i-1}(p-1)=n\prod\limits_{i=1}^r\frac{p-1}{p}$
Jherico
Puntos
12554
Sí, esto puede ser demostrado a través de la inclusión-exclusión , pero es un poco engorroso.
Voy a explicar hasta tres prime-divisores sólo.
En primer lugar recordar que el $1\le a \le n$ es coprime a $n$ cuando no es divisible por cualquier prime $p$ que divide $n$.
Deje $p \mid n$. El número de $1\le a \le n$ tal que $p \mid a$ $n/p$ por lo que el número no divisible por $p$$n - n/p = n(1 - 1/p)$. Por lo que el número de $1\le a \le n$ no divisible por $p$ $ n(1 - 1/p)$ $\varphi(n)$ si $p$ es el único primer dividiendo $n$.
Si tenemos dos números primos $p,q$ dividiendo $n$ y denota el conjunto de los múltiplos $1 \le a \le n$$p$$A_p$, y, asimismo, definir $A_q$, luego tenemos a$|A_p| = n/p$$|A_q| = n/q$$|A_p \cup A_q| = |A_p| + |A_q| - |A_p \cap A_q|$. Ahora $A_p \cap A_q$ es el conjunto de todos los $a$ divisible por $p$$q$, por lo que su cardinalidad es $n/(pq)$.
Por lo tanto $n - |A_p \cup A_q| = n - n/p - n/q + n/(pq)= n (1-1/p)(1-1/q)$. Este es el número de $1 \le a \le n$ no divisible por $p$ o $q$, por lo que es $\varphi (n)$ en el caso de $n$ es divisible sólo por los números primos $p$$q$.
Si ahora tenemos tres números primos $p,q,r$ nos metemos en una manera similar
$|A_p \cup A_q \cup A_r| = |A_p | + |A_q|+ |A_r|- |A_p \cap A_q| - |A_p \cap A_r| - |A_r \cap A_q| + |A_p \cap A_q \cap A_r|$.
Por lo $$n - |A_p \cup A_q \cup A_r|= n - n/p - n/q -n/r + n/(pq) + n/(pr)+ n/(qr)- n/(pqr)= n(1-1/p)(1-1/q)(1-1/r).$$ Y esto es $\varphi(n)$ al $n$ es divisible sólo por $3$ números primos.
