¿Por qué es Euler ' s φ función siempre incluso?

Question

Quiero demostrar por qué es $\phi(n)$ es incluso para $n>3$.

Así que ahora estoy tratando de dividir esto en 2 casos.

Caso 1: $n$ es una potencia de $2$. Por lo tanto $n=2^k$. Por lo $\phi(n)=2^k-2^{k-1}$. Claramente que siempre va a ser incluso.

Caso 2: $n$ no es una potencia de $2$. Aquí es donde yo no estoy seguro de a dónde ir. Me imagino que voy a terminar usando el hecho de que $\phi(n)$ es multiplicativo, y creo que voy a obtener un $(p-1)$ en algún lugar en el producto resultante que va a hacer que todo sea positivo, como $p$ es el primer implica $(p-1)$ es incluso.

Answer 1

Puedes hacerlo a través de la fórmula como usted, pero usted puede también simplemente usar la definición que $\phi(n)$ es el número de números $k$, $1 \le k \le n$, que $\gcd(n, k) = 1$.

Claramente, si $\gcd(k, n) = 1$, entonces el $\gcd(n - k, n) = 1$ así, así (para $n > 2$) todos los números relativamente prima a $n$ pueden emparejar para arriba en pares $\{k, n-k\}$. Así es $\phi(n)$.

Answer 2

Supongamos que $n>3$. Si $n$ tiene un extraño factor principal, decir $p$; entonces $n=p^km,(m,p)=1$ y $\varphi (n)=\varphi(p^k)\varphi(m)=(p-1)p^{k-1}\varphi(m)$, $p-1$ incluso. Si $n$ no tiene ninguna factores primeros impares, entonces $n=2^k$ $k>1$ $\varphi(2^k)=2^{k-1}$ es incluso.

Answer 3

Esta respuesta utilizará algunos un poco más avanzada maquinaria para obtener una respuesta corta.

Si $n\geq 3$ (no necesita asumir entonces $n > 3$) $-1\neq 1$ $\mathbb{Z}/n\mathbb{Z}$ y $(-1)^2 = 1$, $-1$ es un elemento de orden $2$ $(\mathbb{Z}/n\mathbb{Z})^{\times}$, que significa que el $|(\mathbb{Z}/n\mathbb{Z})^{\times}| = \varphi(n)$ es incluso por Lagrange.

Answer 4

Sugerencia $\ $ El mapa de $\,x\mapsto -x\pmod n\,$ no tiene puntos fijos para los pares de seguimiento de los residuos coprime a $n.\,$

Comentario $\ $ uso de este tipo de reflexiones (o involuciones) a la par de términos con frecuencia resulta útil, por ejemplo, ver antes de puestos aquí en la del teorema de Wilson (en grupos), esp. este uno para empezar.

Answer 5

Una prueba utilizando teoría de grupos: Let $Z_n$ denotan el Grupo cíclico de orden $n$. Existe un elemento de orden no trivial 2 de $Aut(Z_n)$ % todo $n>2$, es decir, el mapa de la inversión (aditivo). Desde $|Aut(Z_n)|=\phi(n)$, esto implica que el $\phi(n)$ es para todos $n>2$.