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>.
 
LaPara demostrar la tercera propiedad, sabemos que:
Demostracion:
Sabemos que:
:<math>\varphi(n)=n\prod_{p_i|n}(1-\frac{1}{p_i}) \ con \ p_i \ primo.</math>
Por lo tanto:
:<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>
Como
: <math>
mcd(m,n)=1
</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>
 
:<math>\varphi(n)=n\prod_{p_i|n}\left ( 1-\frac{1}{p_i}) \right con \ p_i \ primo.)</math>
Lo cual implica
 
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>.
 
entoncesComo <math>\operatorname{mcd}(m,n)=1 ningun</math>, entonces primoningun primo entre <math> p_i </math> y <math> q_i </math> son iguales entoncesy 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> seraserá <math> mn=q^{\beta_1}_1q^{\beta_2}_2...q^{\beta_1}_kp^{\alpha_1}_1p^{\alpha_2}_2...p^{\alpha_j}_j </math>, lo cual implica que
 
: <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>
por lo tanto
: <math>
\varphi(mn)=\varphi(m)\varphi(n)
</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.
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>.
 
Con esto, el valor de φ(''n'') puede calcularse empleando el [[teorema fundamental de la Aritmética]]: si