Demuestre que si$n$ es un entero positivo tal que$n\ne 2$ y$n\ne 6$ luego$\phi(n) \ge \sqrt n$

Question

$\phi(n)$ de Euler totient función.

Respecto esfuerzo puesto en el problema:

En el caso de que $n$ es un primer $p$, entonces se le da ese $\phi(p) = p-1$. También se da que $n\ne 2$, por lo que el hecho de que $p-1 \ge \sqrt p$ o $(p-1)^2 \ge p$ es bastante fácil de probar en sí mismo.

Considerando el caso en el que se $n$ es no-el primer número, a continuación, $n$ puede ser escrito como su poder factorización en primos $n=p^{a_1}_1p^{a_2}_2 \ldots p^{a_k}_k$. Se da eso $\phi$ es multiplicativa, por lo que la aplicación de este para el problema original tiene $\phi(n)=\phi(p^{a_1}_1) \phi(p^{a_2}_2) \ldots \phi(p^{a_k}_k)$.

Se da eso $\phi(p^{a_j}_j)=p^j_j-p^{a_j-1}_j=p^{a_j}_j(1-\frac{1}{p_j})$, por lo que la anterior puede escribirse como

$\phi(n)=p^{a_1}_1p^{a_2}_2 \ldots p^{a_k}_k(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k})$.

Que es donde estoy atascado, no acabo de ver cómo probar que el producto arriba indicado (o producto al cuadrado) es mayor que $\sqrt n$ (o $n$ en el producto del cuadrado de caso). Es este el ángulo incorrecto de abordar el problema, o uno de mis inferencias totalmente equivocada?

Answer 1

Lo siento por este ser no muy riguroso y no muy elegante.. como un estudiante de secundaria no conozco muchos "alta potencia" de las herramientas que podría utilizar para resolver esto.

Vamos a tratar de encontrar $n$ que no se ajustan a la norma.

La proposición: vamos a obtener nuestra mejor apuesta en la falsificación de la declaración de entre primorials, es decir, aquellos números de la forma $\displaystyle \prod_{n = 1}^k p_n$

Considerar cuando no es una primorial.

Caso 1: se añade un $p_i$ a nuestro primorial $p_k \#$$i < k$. En otras palabras, $n$ tiene un factor repetido. A continuación,$p_i \phi(n) = \phi (np_i)$. Por lo tanto, al hacer esto, se aumento el lado izquierdo por $p_i$, mientras que el aumento de nuestra mano derecha sólo por $\sqrt p_i$, por lo que este es improductivo. Conclusión, tenemos a más de uno de cualquier factor principal en la $n$.

Caso 2: ¿y si no tomamos el más pequeño de los números primos. Lo que si hemos cambiado un factor de $p_i$ $p_k \#$ a una $p_j$$i < k <j$? A continuación, se aumentaría el lado izquierdo por un factor de $(\frac{p_j}{p_i})(\frac{p_i}{p_i-1})(\frac{p_j-1}{p_j})$, mientras que el aumento de la mano izquierda por un menor factor de $\sqrt{\frac{p_j}{p_i}}$. Conclusión, podemos tomar el más pequeño de los números primos podemos.

Además, una vez que nos encontramos con una primorial que trabaja para la instrucción, todos los más primorials trabajo así. Considerar si $p_i \#$ no funciona, es decir,$\phi(p_i \#) \geq \sqrt{p_i \#}$. A continuación,$\phi (p_{i+1} \#) = \phi(p_{i+1})\phi(p_i \#) \geq \sqrt{p_{i+1}} \sqrt{p_i \#}$, ya que el $\phi(p_{i+1}) = p_{i+1} - 1 \geq \sqrt{p_{i+1}}$ todos los $i \geq 1$

Así, mediante la inspección nos encontramos con $n = 2, n = 6$ no trabajan. $n = 24$ funciona porque $6 \geq \sqrt{24}$, así que no hay más primorials trabajo.

Para terminar, sólo tenemos que hacer algo de inspección en $n =2$ $n = 6$ para asegurarse de que las variaciones de ellos trabajan. Para $n = 2$, comprobamos $2^2$, y encontrar que $\phi (4) = 2 \geq 2$ obras. Para $n = 6$, comprobamos $2^2 \times 3$$2 \times 3^2$, y parece que ambos de ellos trabajan. Por lo tanto, $n = 2, n = 6$ son sólo números enteros $n$ que no cumplen con la norma.