Mostrar que $\frac n {\phi{(n)}}\le r+1$, donde $r$ es el número de factores primeros distintos de $n$.

Question

Mostrar que $\frac n {\phi{(n)}}\le r+1$, donde $r$ es el número de factores primeros distintos de $n$.

Solo tengo la idea de que la flor de #%-th $i$% #% hasta ahora.

Answer 1

Tenemos $$ \frac{\phi(n)} {n} = \prod_{p|n} \left (1-\frac{1}{p} \right).$$ así, $$ \frac{n}{\phi(n)} = \prod_{p|n} \frac{p}{p-1} \le \prod_{i=2}^{1+\omega(n)} \frac{i}{i-1} = 1 + \omega(n)$ $ $\omega(n)$ Dónde está el número de divisores distintos principal de $n$.

La idea es sustituir el producto por números primos un producto sobre todos enteros a la desigualdad, que utiliza su idea que prime el $n$-th es mayor o igual a $n+1$.

Answer 2

Empezar con $n$ tal que $r=1$ (como en el caso base). Entonces, desde el $\phi(n)=n-1$ (porque aquí $n$ es un prime) $$\frac{n}{\phi(n)}=\frac{n}{n-1}\leq1+1.$$ Supongamos que para $n$ $r=i$ $$\frac{n}{\phi(n)}\leq i+1.$$ Multiplicando la ecuación anterior por $p^k$ (una nueva distintos primer factor a algunos de potencia $k$), $$\frac{n\;p^k}{\phi(n)}\leq (i+1)p^k,$$ y dividiendo por $\phi(p^k)$, $$\frac{n\;p^k}{\phi(n)\phi(p^k)}\leq \frac{(i+1)p^k}{\phi(p^k)}.$$ Para demostrar el proceso iterativo de paso, usamos el hecho de que para $p$ un primo, $$\phi(p^k)=p^k\left(1-\frac{1}{p}\right),$$ y el hecho de que $\phi$ es una función multiplicativa, llegando a $$\frac{n\;p^k}{\phi(n\;p^k)}\leq (i+1)\frac{p}{p-1}\leq (i+1)+1.$$

La última desigualdad se utiliza el hecho de que $p$, $(i+1)^{\text{th}}$ prime, es $\geq (i+2)$.