Propiedades de la función totiente de euler

Question

¿Por qué la función totiente de euler tiene la siguiente condición de verdad basada en su definición?

$$ \phi(p^k)=p^{k-1}(p-1) = p^k(1-\frac{1}{p}) = p^k-p^{k-1} $$

¡Una prueba sería impresionante y una intuición de por qué esto es cierto sería aún mejor!

(para demostrarlo pensé en usar la multiplicatividad de la función totiente pero eso no funcionaría porque p no es coprima a sí misma :( )

Una explicación más detallada del artículo de la wikipedia obtendrá un like y una respuesta aceptada.

Para que te acepten, dar una explicación de por qué el número de múltiplos de p es $p^{k-1}$ será un factor importante. Además, ¿los múltiplos de p que estamos excluyendo están entre 1 y $p^k - 1$ o a $p^k$ ?

Es necesario contar con algún tipo de argumento para ser aceptado.

Answer 1

Cualquier número entero positivo $x$ menos de $p^k$ puede escribirse en base $p$ como $$ x = a_0 + a_1 p + a_2 p^2 + \cdots + a_{k-1} p^{k-1} $$ donde $a_i \in \{0, 1, 2, \ldots, p-1\}$ . Entonces $x$ no es relativamente primo de $p^k$ si $p \mid x$ si $a_0 = 0$ . Por lo tanto, si queremos $x$ para ser relativamente primo a $p^k$ tenemos $p-1$ opciones para $a_0$ y $p$ opciones para cada uno de los otros $k-1$ coeficientes, por lo que $\varphi(p^k) = (p-1)p^{k-1}$ .

Answer 2

Aquí está intiution....

Toma $p^2$ . ¿Cuántos números en el rango $1 \ldots p^2$ son no ¿Co-prima a la misma? Son precisamente $p$ , $2p$ , $3p$ ... $p^2$ . Hay exactamente $p$ de ellos. Así que el número co prime a $p^2$ es $$ \phi(p^2) = p^2 -p = p (p-1)$$

Puede hacer lo mismo para $p^3$ para conseguir $$ \phi(p^3) = p^3 -p^2 = p^2 (p-1)$$

Puedes convertir esto en una prueba por inducción si lo deseas.

Answer 3

Me parece intuitivo pensar en términos de "cuáles son las posibilidades de no ser coprimo de $p^k$ ?"

Una vez que te das cuenta de que "coprime to $p^k$ "es sinónimo de "no divisible por $p$ ", sugiere la proporción de números hasta $p^k$ que son coprimos a $p^k$ es $1 - \frac1p$ motivando la cantidad $p^k(1-\frac1p)$ .

El mismo razonamiento se aplica a la $n$ (pero requiere más esfuerzo para justificar cuidadosamente): "coprima a $n$ "es sinónimo de "no divisible por ninguno de los factores primos de $n$ ", y si puedes convencerte de que las probabilidades individuales son independientes esto sugiere $\phi(n) = n\prod_{p\mid n} (1-\frac1p)$ .

Answer 4

Otra explicación (gran parte de la cual está implícita en las otras respuestas):

Un número $n$ es no coprima a $p \iff \text{gcd}(p,n) \neq 1 \iff \text{gcd}(p,n) = p \iff n$ es un múltiplo de $p$ . Ahora los múltiplos de $p$ entre $1$ y $p^k$ son precisamente los números $mp$ , para $1 \leq m \leq p^{k-1}$ de los cuales hay $p^{k-1}$ . Al restarlos del total se obtiene $p^k - p^{k-1} = \phi(p^k)$ .

Answer 5

$p^k$ sólo comparte factores comunes con otros múltiplos de $p$ . ¿Cuántos múltiplos de $p$ están ahí bajo $p^k$ ?: $\frac{p^k}{p}=p^{k-1}$ Sólo hay que ver el 8, por ejemplo. Hay 4 múltiplos de 2 por debajo del 8. Para obtener el valor del totiente por definición excluir de $p^k$ todos los valores bajo ella que comparten un factor común, de los cuales hay $p^{k-1}$ .