Diferència entre revisions de la pàgina «Funció φ d'Euler»

m (Robot insereix {{ORDENA:Funcio D'Euler}})
<math>\phi(n)=\prod_{i=1}^k p_i^{e_i-1}*(p_i-1)</math>
 
Aquesta funció revelacompta quants nombres menors que ''n'' són coprimers amb ''n'', és a dir, quants nombres més petits que ''n'' no comparteixen cap primer amb ''n'' en la seva factorització.
La demostració d'aquesta funció es realitzarà segons els nombres naturals menors que ''n''. Efectivament, si es dibuixa una recta que contingui tots els valors des de 0 fins a n podem marcar en aquesta tots els ''primers'' que pertanyen a n, així com les seves potències (fins a l'e<sub>i</sub> corresponent). Fet això procedim al següent raonament: sigui el nombre ''n'', la quantitat de nombres que seran coprimers amb aquest serà ''n'' menys una certa quantitat, així doncs trobar <math>\phi</math>(n) serà equivalent a trobar aquesta certa quantitat. Es parteix del fet que qualsevol nombre que tingui a la seva factorització algun dels ''primers'' de ''n'' no serà coprimer, així doncs descartem inicialment els nombres resultants de dividir ''n'' entre qualsevol dels seus ''primers'', aquesta quantitat serà a<sub>1</sub>. A continuació descartem els que siguin resultat de dividir ''n'' pel producte de dos dels seus primers, aquest resultat l'anomenarem a<sub>2</sub>. Fent servir aquest mètode iterativament s'arriba a l'expressió següent:
:<math>\phi'(n)=n-\sum_{i=1}^{k} a_i</math>
Usuari anònim