Diferencia entre revisiones de «Función φ de Euler»
Contenido eliminado Contenido añadido
Línea 17:
La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus anteriores. Y, por tanto, existen ''p''-1 elementos coprimos con ''p''.
La segunda propiedad se demuestra por [[inducción matemática|inducción]], supongamos que ''k'' = 1. Entonces <math>\varphi(p^1) = \varphi(p) = p-1</math> por la propiedad 1, de manera que se puede escribir como <math>\varphi(p^1) = (p-1)p^{1-1}</math>. Se debe demostrar que se cumple para <math>\varphi(p^{k+1}) = (p-1)p^k</math>. Reescribiendo la identidad, <math>(p-1)p^k = (p-1)p^{k-1}p</math>, luego <math>((p-1)p^{k-1})p = \varphi(p^k)p</math>. Como <math>\varphi(p^k)</math> es la cantidad de números coprimos con <math>p^k</math>, si multiplicamos dicha cantidad por ''p'', el número que es coprimo con los demás debe aumentar ''p'' veces, con lo que <math>\varphi(p^{k})p=\varphi(p^{k+1})=(p-1)p^k</math>.
:<math>\varphi(n)=n\prod_{p_i|n}(1-\frac{1}{p_i}) \ con \ p_i \ primo.</math>▼
:<math>\varphi(n)\varphi(m)=mn\prod_{p_i|n}(1-\frac{1}{p_i})\prod_{q_i|n}(1-\frac{1}{q_i})</math>▼
entonces ningun primo entre <math> p_i </math> y <math> q_i </math> son iguales entonces la descomposición en primos de <math> mn </math> no se ve alterada, es decir si <math> m=q^{\beta_1}_1q^{\beta_2}_2...q^{\beta_1}_k </math> y <math> n=p^{\alpha_1}_1p^{\alpha_2}_2...p^{\alpha_j}_j </math> entonces la descomposicion en primos de <math> mn </math> sera <math> mn=q^{\beta_1}_1q^{\beta_2}_2...q^{\beta_1}_kp^{\alpha_1}_1p^{\alpha_2}_2...p^{\alpha_j}_j </math>▼
con ''p''<sub>''i''</sub> primo, por tanto:
▲:<math>\varphi(n)\varphi(m) = mn\prod_{p_i|n}\left ( 1-\frac{1}{p_i}\right ) \prod_{q_i|n}\left ( 1-\frac{1}{q_i} \right )</math>.
▲
: <math>
\varphi(mn)=mn\prod_{p_i|n}\left ( 1-\frac{1}{p_i} \right ) \prod_{q_i|n}\left ( 1-\frac{1}{q_i} \right )
</math>
si <math> m </math> y <math> n </math> son primos relativos.▼
▲por lo tanto, <math>\varphi(mn)=\varphi(m)\varphi(n)</math> si <math> m </math> y <math> n </math> son primos relativos.
Con esto, el valor de φ(''n'') puede calcularse empleando el [[teorema fundamental de la Aritmética]]: si
|