Funció φ d'Euler: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m neteja i estandardització de codi |
||
Línia 49:
<math>\phi(n)=\prod_{i=1}^k p_i^{e_i-1}*(p_i-1)</math>
Aquesta funció compta quants nombres menors que ''n'' són [[Nombres_coprimers|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>
Línia 169:
<math>a^{\phi(n)}=1mod(n)</math>
A on tal com ja s'ha dit abans <math>\phi(n)</math> és la funció d'Euler. Ara només resta demostrar que la cardinalitat de la resta de generadors és divisor de la del generador primari.
En efecte, si un element genera la totalitat d'elements invertibles podrem posar qualsevol element invertible com a potència del generador, per tant:
| |||