Es decir, ¿por qué es $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, si a y B son coprime? No es sólo una técnica de problemas-no veo por qué esto debería ser, de forma intuitiva: yo bellyfeel que su multiplicativity debe ser una aproximación a la mayoría. Y por qué el valor mínimo de $\varphi (n)$ debe $ \frac{4n}{15} $ completamente me pasa.
Respuestas
¿Demasiados anuncios?
En general, si $R$ $S$ son anillos, a continuación, $R\times S$ es un anillo. Las unidades de $R\times S$ son los elementos $(r,s)$ $r$ una unidad de $R$ $s$ una unidad de $S$. Si $R$ $S$ son finitos, los anillos, el número de unidades en $R\times S$ es por lo tanto el número de unidades en $R$ multiplicado por el número de unidades en $S$.
Ahora si $\gcd(A,B)=1$, $$\mathbb Z/\left<AB\right> \cong \mathbb Z/\left<A\right> \times \mathbb Z/\left<B\right>$$
Este es esencialmente el teorema del resto Chino.
Pero el número de unidades en el anillo de $\mathbb Z/\left<n\right>$$\phi(n)$. Por lo que el número de unidades en $\mathbb Z/\left<AB\right>$ $\phi(AB)$ y el número de unidades en $\mathbb Z/\left<A\right> \times \mathbb Z/\left<B\right>$ $\phi(A)\phi(B)$
Dave Cahill
Puntos
53
$n = \prod_{k=1}^{z}p_{k}^{e_{k}}$
$\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$
Deje $a=\prod_{k=1}^{w} p_{k}^{e_{k}}$
Deje $b=\prod_{k=w+1}^{z} p_{k}^{e_{k}}$
$n=ab$
$\varphi(a) = a\prod_{k=1}^{w}(1-\frac{1}{p_{k}})$
$\varphi(b) = b\prod_{k=w+1}^{z}(1-\frac{1}{p_{k}})$
$\varphi(a)\varphi(b) = ab\prod_{k=1}^{w}(1-\frac{1}{p_{k}}) \cdot \prod_{k=w+1}^{z}(1-\frac{1}{p_{k}})$
$\varphi(a)\varphi(b) = ab\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$
$\varphi(a)\varphi(b) = n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$
$\varphi(a)\varphi(b) =\varphi(n)$
$\varphi(a)\varphi(b) =\varphi(ab)$
DiGi
Puntos
1925
Esto sólo se aborda la noción errónea de que $\frac{\varphi(n)}n$ tiene un resultado positivo en el límite inferior, pero es demasiado largo para un comentario.
Si $m_n=p_1\dots p_n$ es el producto de la primera $n$ de los números primos, a continuación,$\varphi(m_n)=\prod\limits_{k=1}^np_k\left(1-\frac1{p_k}\right)$, e $$\frac{\varphi(m_n)}{m_n}=\prod_{k=1}^n\left(1-\frac1{p_k}\right)\;.$$
Considere la posibilidad de la reciprocidad,
$$\begin{align*} \frac{m_n}{\varphi(m_n)}&=\prod_{k=1}^n\left(\frac1{1-p_k^{-1}}\right)\\ &=\prod_{k=1}^n\sum_{i\ge 0}\frac1{p_k^i}\\ &\ge\prod_{k=1}^n\left(1+\frac1{p_k}\right)\;. \end{align*}$$
Para los positivos $a_k$ el infinito producto $\prod_{k\ge 1}(1+a_k)$ converge iff la serie $\sum_{k\ge 1}a_k$ converge, y es bien sabido que el $\sum_{k\ge 1}\frac1{p_k}$ diverge, por lo $\lim_{n\to\infty}\frac{m_n}{\varphi(m_n)}\to\infty$, y por lo tanto $\lim_{n\to\infty}\frac{\varphi(m_n)}{m_n}=0$.
Lockie
Puntos
636
En general, es verdad que el $\Phi(AB)\neq\Phi(A)\Phi(B)$--por ejemplo, $\Phi(8)=4$, pero $\Phi(2)=1$$\Phi(4)=2$. A lo mejor, por lo general, podemos decir que la $\Phi(AB)\geq\Phi(A)\Phi(B)$. Nos va a haber igualdad cuando (y sólo cuando) $A,B$ son coprime, aunque.
Deje $R_1,R_2$ ser anillos, y tenga en cuenta que $R_1\times R_2$ también es un anillo con las componentes de la adición y la multiplicación. Un determinado $(x_1,x_2)\in R_1\times R_2$ tiene un inverso multiplicativo si y sólo si el $x_k$ tienen inversos multiplicativos en $R_k$.
Tenga en cuenta que los números enteros $A,B$ son coprime si y sólo si existen enteros $X,Y$ tal que $AX+BY=1$ si y sólo si $A$ tiene un inverso multiplicativo modulo $B$ $B$ tiene un modulo $A$. Por lo tanto, no son, precisamente, $\Phi(A)$ elementos de $\Bbb Z/A\Bbb Z$ tienen inverso multiplicativo.
Por la discusión anterior, $\Bbb Z/AB\Bbb Z$ tienen $\Phi(AB)$ elementos con los inversos multiplicativos, y $(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$ tienen $\Phi(A)\Phi(B)$ de dichos elementos.
La única cosa que queda por demostrar es que no es un bijection (de hecho, un isomorfismo) entre $\Bbb Z/AB\Bbb Z$$(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$. Que $A,B$ son coprime es crucial para la prueba, así que asegúrese de usar! Me gustaría empezar con el natural homomorphism $\Bbb Z\to(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$$X\mapsto(X\,mod\, A,X\, mod\, B)$, que fácilmente se ha kernel $AB\Bbb Z$, y, a continuación, utilizar la coprimality de $A,B$ surjectivity, por lo que la conclusión deseada de la siguiente manera por el Primer Teorema de Isomorfismo.
Edit: Su adición es incorrecta. El $\frac{4n}{15}$ límite inferior se obtiene cuando estamos mirando el primer $100$ valores de $\Phi(n)$--alcanzado por $30,60,90$, pero es engañoso. Hay números más allá de lo que caiga por debajo de esa obligados, tales como $210$. Hay, de hecho, no menor de delimitación línea recta de pendiente positiva que pasa por el origen que se aplica a todos los enteros.
runeh
Puntos
1304
Si $n=p_1^{a_1}p_2^{a^2} \dots p_r^{a_r}$ $p_i$ distintos de los números primos (por ejemplo, en orden creciente para obtener la forma canónica) y el $a_i$ enteros positivos, entonces tenemos:$$\phi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dots\left(1-\frac1{p_r}\right)$$ (vale la pena trabajar por ti mismo)) entonces si $m$ $n$ co-prime en los diferentes factores para sus respectivos primos divisores y el multiplicativity es fácil de ver. Si se tiene en cuenta que la suma de los recíprocos de los números primos es infinito, usted será capaz de ver que se puede hacer el primer bit del producto como pequeño como quieras (por ejemplo, tomar registros), por lo que el $\frac{\phi(n)}n$ puede hacerse tan pequeño como sea posible. Usted será capaz de elegir los valores de $n$ que hacen de esta fracción en particular de las pequeñas. Menciono esta expresión para $\phi(n)$ porque es el que más ha ayudado en mi intuición.
