Prueba de la fórmula de Euler ' función φ

Question

Leí en un foro en algún lugar que la función de φ puede ser calculada por encontrar el producto de menos de cada uno de los factores primeros del número. Por ejemplo, para encontrar el $\phi(30)$, calcular $(2-1)\times (3-1)\times (5-1) = 8$.

Me parece no conseguir mi cabeza alrededor de por qué esto funciona y no sé qué escribir en Google para encontrar una prueba formal. Alguien podria por favor explicarme en un fácil de comprender por qué esto funciona.

Answer 1

Por definición, $\phi(30)$ es el número de números menos de $30$ primer junto a él. Además, $\phi(abc) = \phi(a)\times \phi(b)\times \phi(c)$. Tenga en cuenta que $\phi(p)$ para todos números primos siempre es $p - 1$ porque hay $p - 1$ números menos que cualquier dado % primer $p$y todos los números menos que un primer son coprimos a él.

Esto quiere decir $\phi(30) = \phi(2\cdot 3 \cdot 5) = \phi(2) \cdot \phi(3) \cdot \phi(5) = (2-1)(3-1)(5-1) = 8$. Pero $\phi(60) = 16 \ne (2 - 1)(3 - 1)(5 - 1)$ lo que dije no siempre es cierto. Es cierto sólo si tienes un % de orden $1$de todos los divisores primeros.

Answer 2

En primer lugar, la función φ es multiplicativo

Si $N=\prod_{1\le r\le n}p_r^{a_i},\phi(N)=\prod_{1\le r\le n}\phi(p_r^{a_i})$ donde $p_i$ son números primos distintos y $a_i$ son enteros positivos.

Ahora, es relativamente alto con cualquier número que no es divisible por $p_r^{a_i}$ $p_r$

El número de números son divisibles por $\le p_r^{a_i}$ $p_r$ y es $\frac{p_r^{a_i}}{p_r}=p_r^{a_i-1}$

Por lo tanto, es igual a $\phi(p_r^{a_i})$ $p_r^{a_i}-p_r^{a_i-1}=p_r^{a_i-1}(p_r-1)$

Answer 3

Este trabajo sólo si el $n$ es squarefree ($30=2\cdot3\cdot5$ es squarefree).
Se puede probar eso si $n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}$ (donde $p_i$ son primos entonces $p_i\neq p_j \ \forall i\neq j$) $$\phi(n)=p_1^{k_1-1}\cdot p_2^{k_2-1}\cdots p_r^{k_r-1}\cdot(p_1-1)\cdot(p_2-1)\cdots(p_r-1).$ $ por lo tanto si $n$ es squarefree entero, lo que significa que el $k_i=1 \ \forall \ i=1,2,\ldots r$,$$ \phi(n)=(p_1-1)\cdot(p_2-1)\cdots(p_r-1).

Ver este.

Answer 4

Aquí está una explicación alternativa que algunos podrían encontrar fácil de entender. La fracción $\phi(n)/n$ representa la probabilidad de que un número aleatorio $k$ elegido de $\{1,\ldots,n\}$ es relativamente primer a $n$. Este evento se produce, precisamente, cuando se $k$ no es divisible por ninguno de los factores primos de a $n$.

Para cada uno de los prime $p$ dividiendo $n$, vamos a $E_p$ ser el caso de que $k$ es divisible por $p$. Tenga en cuenta que $\mathbb P(E_p) = \tfrac1p$ (se puede ver por qué esto es sólo precisa cuando se $p$ divide $n$?).

El paso clave es utilizar el Teorema del Resto Chino a ver que si $p_1, p_2, \ldots, p_r$ son cualquier distintos números primos dividiendo $n$, entonces los eventos $E_{p_1}, E_{p_2}, \ldots, E_{p_r}$ son independientes: aún no afecta a sus posibilidades de ser divisible por $3$ (de nuevo, tenga en cuenta que esto sólo es precisamente cierto, porque la $n$ es un múltiplo de la MCM de los números primos).

En particular, se puede elegir también el $p_1, p_2, \ldots, p_r$ a todos los números primos dividiendo $n$. En este caso, ya que los $\phi(n)/n$ es la probabilidad de que ninguno de estos eventos ocurre, tenemos

$$\frac{\phi(n)}{n} = \mathbb P(\overline{E_{p_1}} \cap \overline{E_{p_2}} \cap \cdots\cap\overline{E_{p_r}}) = \mathbb P(\overline{E_{p_1}})\mathbb P(\overline{E_{p_2}})\cdots \mathbb P(\overline{E_{p_r}}) = (1-\tfrac1{p_1})(1-\tfrac1{p_2})\cdots(1-\tfrac1{p_r}).$$

Answer 5

% Toque $\ $examen unidades (invertibles) en el % de descomposición CRT $\rm\: \Bbb Z/n \cong \Bbb Z/p^j \oplus \cdots \oplus \Bbb Z/q^k \:$muestra que $\rm\:\phi(n) = \phi(p^j)\cdots \phi(q^k),\:$ y uno fácilmente % unidades $\rm\:\phi(p^j) = p^j - p^{j-1} = p^{j-1}(p-1)\:$contando (no) mod $\rm\,p^j;$ son números enteros en $\rm[1,p^j]$ que no coprime $\rm\,p,\,$ por lo tanto, son precisamente el $\rm\,\color{#C00}{p^{j-1}}$ múltiplos de $\rm\,p \le p^j,\:$ $\rm\: \color{#C00}1\cdot p,\: \color{#C00}2\cdot p,\ldots,\:\color{#C00}{p^{j-1}}\cdot p.$