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

m
Correcció lingüística
m (Robot: Reemplaçament automàtic de text (-{{millorar text +{{millorar text|data=abril de 2013))
m (Correcció lingüística)
 
=== Natura de l'anell <math>(\mathbb{Z}_n,+,*)</math> ===
Qualsevol congruència mòdul està formada, tal i com ja s'ha esmentat, pel ròssec de qualsevol nombre vers l'índex de la congruència, la pregunta és: existeix alguna relació entre els diversos nombres que conformen la congruència en qüestió? És possible establir alguna mena de relació entre tots aquests nombres?
 
La resposta a aquestes preguntes rau en el caràcter cíclic de l'anell, tot tenint en compte que, donat que hi ha elements que no tenen inversa respecte el producte, només es tractarà amb els elements que sí que en tenen.
 
== Funció Fi d'Euler ==
La funció Fi d'Euler, tal i com s'ha descrit, es pot denotar matemàticament com:
<math>\phi(n)=\prod_{i=1}^k p_i^{e_i-1}*(p_i-1)</math>
 
<math>k1_{max}=\frac{36}{2}</math> i <math>k2_{max}=\frac{36}{3}</math>
 
Tal i com s'ha explicat abans, si tenim en compte aquesta col·lecció de nombres a extreure dels candidats a ser coprimers, comptarem dues vegades nombres de la forma:
 
<math>A_1'=2*3*k1'</math> i <math>A_2'=3*2*k2'={6,12,24...}</math>
A on la funció <math>\mu(n/d)</math> és la funció de Möbius, i ''d'' són els divisors de ''n''. Com en el cas anterior, les dmostracions d'ambdues fòrmules segueixen patrons semblants als emprats en la demostrció de la funció Fi d'Euler. Com a nota orientativa cap al lector, dir que en la demostració de la primera identitat es fa servir el fet que, al ser ''d'' divisor de ''n'', part del grup de coprimers amb ''n'' pertany també als de ''d''. En el cas de la segona identitat cal saber la definició de la [[funció de Möbius]], i tot aplicant-la, la identitat surt de manera natural.
 
Com a darrer apunt dins aquest apartat, fixem-nos en la relació que manté la funció Phi d'Euler en la distribució en la recta natural que segueixen els nombres primers. Tal i com ja s'ha dit, la funció Phi d'Euler dóna el nombre d'elements coprimers a un donat menors que aquest, això és tan com dir el nombre de possibles combinacions de nombres primers, no pertanyents a la factorització de la referència, que donen lloc a d'altres nombres menors que la referència (que al llarg de l'article s'ha denotat com a ''n''). Per tant aquesta funció ha de ser certament proporcional a la quantitat de nombres primers diferents als de la factorització de ''n'', i com aquests darrers els tenim fixats, <math>\frac{\phi(n)}{n}</math> ens descriurà la densitat la densitat de nombres primers.
 
== Teorema de Euler-Fermat ==
 
Tal i com ja s'ha apuntat anteriorment, la funció d'Euler té diverses aplicacions, entre les quals destaca el conegut com a Teorema d'Euler-Fermat, també conegut com a ''petit teorema de Fermat'' o ''Conjectura Xinesa''. Aquesta afirma que:
 
:<math>a^{\Phi(n)}=1 mod(n)</math>
=== Teorema d'Euler-Fermat ===
 
Sigui un element invertible, el conjunt d'elements que generarà serà òbviament finit (ja que es tracta amb conjunts finits) i de cardinalitat igual o inferior a la del conjunt total d'elemnts invertibles de l'anell <math>(\mathbb{Z}_n,+,*)</math>; fóra interessant però saber quina serà la mida del conjunt generat. Supòsis que existeix un element tal que pot generar la totalitat d'elements invertibles, tal i com ja s'ha dit un element serà invertible si i només si és coprimer amb l'índex de la congruència, així doncs tal i com s'ha apuntat amb anterioritat la mida del conjunt generat serà precisament <math>\phi(n)</math>, dit d'una altra manera:
 
<math>C(<a>)=\phi(n)</math>
<math>a^{\phi(n)}=1mod(n)</math>
 
A on tal i 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:
 
851.856

modificacions