¿El totient función de alcanzar todos sus valores cuando se limita a los números impares?

Question

Esta pregunta podría ser un duplicado, si es así, me disculpo de antemano. Es simple, pero respondiendo él es probablemente más difícil :)

Es cierto, que el $\phi(n)$ (función de Euler totient función) toma todos sus valores, al $n$ es un entero impar?

Yo, obviamente, probé por primera algunos $n$:

$\phi(1) = 1, \phi(3) = 2, \phi(5) = 4, $ y así sucesivamente.

Es obvio, que si $n$ es un número primo, de $\phi(n) = n-1$, de modo que se cubran todas las $p-1$ números, donde $p$ es un primo. Yo simplemente no puede demostrar realmente si cualquier número que falta en esta lista.

La cuestión se puede plantear de esta manera: ¿Es verdad, que si utilizamos el totient función con sólo números enteros impares, podemos obtener todos los valores de se. Espero que usted pueda entender, si no, solo un comentario más abajo, y trato de responder. :) Gracias por los comentarios!

Answer 1

La respuesta es no por ningún número impar $n$ podemos tener $\varphi(n)=2^{32}$, aunque $\varphi(2^{33})=2^{32}$. Suponiendo que hay un $n$ si $n=p_1^{e_1}...p_i^{e_i}$ (con todos los primos impares), a continuación,$\varphi(n)=\varphi(p_1^{e_1})...\varphi(p_i^{e_i})=p_1^{e_1-1}(p_1-1)...p_i^{e_i-1}(p_i-1)$. Si alguna de las $e_k>1$ entonces tendríamos $\varphi(n)$ divisible por $p_k$, por lo que no podía ser igual a $2^{32}$. Así que cada $e_k=1$, y todas las $p_k-1$ son potencias de dos, por lo que el $p_k$ son primos de Fermat, decir $p_k=F_{a_k}=2^{2^{a_k}}+1$. Así que tenemos $2^{32}=\varphi(n)=2^{2^{a_1}}...2^{2^{a_i}}=2^{2^{a_1}+...+2^{a_i}}$, lo $32=2^{a_1}+...+2^{a_i}$. Por la singularidad de los binarios de expansión, obtenemos $i=1$$a_1=5$, pero después tenemos que $F_5=2^{2^5}+1$ es primo, que no lo es. Contradicción.

Answer 2

No.
$\let\phi\varphi\let\leq\leqslant$ Observa que si $\phi(n)=2^k$ $n$ es impar, entonces todos los primos divisores de $n$ son primos de Fermat (los números primos de la forma $F_a=2^{2^a}+1$) y tienen una multiplicidad $1$. El único conocido de los números primos de Fermat corresponden a $a=0,1,2,3,4$, y se sabe que $5\leq a\leq32$ da compuesto de números.
La reclamación. No existe ningún número impar $n$$\phi(n)=2^{32}$.
Prueba. Cada divisor primo de $n$ es una de Fermat prime $F_a$ $a\leq5$ y tiene multiplicidad $1$. Por lo tanto el único posible primos divisores de $n$$F_0,F_1,F_2,F_3,F_4$. Pero $\phi(F_0F_1F_2F_3F_4)=2^{1+2+4+8+16}=2^{31}$, lo que significa que las $n$ no puede existir.

Answer 3

La respuesta es no. Deje $m = 2^kn$, $k=3$ o $4<k<15$ $n$ impar. A continuación,$\phi(m) = \phi(2^k)\phi(n)=2^{k-1}\phi(n)$. Yo afirmación de que no hay número impar $x$$\phi(x) = \phi(m) = 2^{k-1}\phi(n)$.

Deje $x$ ser un número impar. Puede ser escrita como $\Pi_{i=1}^n p_i^{e_i}$, donde debido a $x$ es impar, ninguno de los $p_i$$2$. La fórmula para el totient dado una descomposición en factores primos de los rendimientos de $\phi(x) = \Pi_{i=1}^n p_i^{e_i-1}(p_i-1)$.

$p_i^{e_i-1}$ está claro que no es una potencia de dos por $p_i \neq 2$, e $(p_i-1)$ es una potencia de dos, sólo para $p_i$ un Fermat prime. El único conocido de los números primos son $3,5,17,257, 65537$. Esto significa que la única conocida potencias de dos que pueden aparecer en $\phi(x)$ $2,4,16,256,65536$ o $2^1,2^2,2^4,2^{16}$. Así que si $k =4$ o $5<k<17$, $\phi(x)$ no puede igualar $\phi(2^kn)$.