Funció φ d'Euler: diferència entre les revisions

<math>\phi(n)=\prod_{i=1}^k p_i^{e_i-1}*(p_i-1)</math>

 

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_i 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₁. A continuació descartem els que siguin resultat de dividir ''n'' pel producte de dos dels seus primers, aquest resultat l'anomenarem a₂. Fent servir aquest mètode iterativament s'arriba a l'expressió següent:

:<math>\phi'(n)=n-\sum_{i=1}^{k} a_i</math>