Funció φ d'Euler

La funció φ (fi) d'Euler va sorgir de manera natural durant l'estudi que el matemàtic Leonhard Euler va mantenir sobre la natura dels nombres naturals, i més concretament sobre la natura de les congruències modulars ℤ/nℤ. Arran d'aquest estudi es van anar succeint una sèrie de resultats tals com el teorema de Fermat-Euler, la mateixa funció φ d'Euler o la classificació dels anomenats generadors de congruències modulars.

Els primers mil valors de $φ (n)$ . Els punts de la línia superior representen $φ (p)$ quan $p$ és un nombre primer, que és $p - 1.$ ^[1]

Avui dia tots aquests resultats s'apliquen en camps tan diversos com la criptografia (vegeu algorisme d'encriptació RSA), la pròpia teoria de nombres (vegeu grups cíclics, congruències i teoria de categories de representacions en general) o com a eina d'optimització d'algorismes de programació.

Entorn matemàtic

La funció Fi d'Euler s'emmarca dins de l'anomenada teoria de conjunts, i més concretament, dins de les congruències mòdul, amb una descripció matemàtica com la que segueix.

Una congruència mòdul $Z_{n}$ és un conjunt i, per tant, està regida per la natura dels conjunts. Aquest està format exactament per n elements que són justament la col·lecció:

{0,...,n-1}

A l'hora de construir aquest conjunt l'eina que es fa servir és la del conjunt quocient. Un conjunt quocient és una relació d'equivalència entre altres dos conjunts. En el cas de les congruències mòdul, la relació d'equivalència és evident: es relacionen uns elements amb d'altres segons la seva diferència, així les coses, s'associa qualsevol n amb el seu "representant" a ${0,...,m-1}$ segons el valor que faci que la diferència recaigui sobre el nucli de l'aplicació, en altres paraules, a cada nombre se li resta k vegades l'índex de la congruència mòdul. Un exemple d'això fóra: a $Z_{5}$ el nombre quaranta-vuit se'l representa mitjançant la relació d'equivalència corresponent amb $48-k*5=48-9*5=3$

Algebraicament les congruències mòdul venen representades per:

(\mathbb {Z} )/(\mathbb {Z} *n)=\mathbb {Z} _{n}

En la pràctica però, la construcció de les congruències mòdul es fa a partir de l'anomenat ròssec de la divisió de qualsevol nombre per l'índex de la congruència n.

La congruència mòdul, en tant que conjunt, segueix les propietats associativa, existència d'element neutre i existència d'element invers (aquesta darrera propietat només s'acomplirà per a certs elements del conjunt en el cas del segon operador: el producte habitual). Cal remarcar que la propietat d'existència d'element invers és el rovell de l'ou de tot el problema, ja que el comportament del conjunt quedarà determinat per l'element invers.

Es treballa doncs amb el conjunt $(\mathbb {Z} _{n},*)$ amb l'operador intern el producte habitual. Val la pena comentar que, per a obtindre $(\mathbb {Z} _{n},*)$ , es parteix de $(\mathbb {Z} ,+)$ , i que el que es fa és esdevenir d'un conjunt un anell format per la terna $(\mathbb {Z} _{n},+,*)$ , de manera que, tot i que certs elements no tenen inversa, no es trenca en cap cas l'àlgebra del conjunt.

Natura de l'anell $(\mathbb {Z} _{n},+,*)$

Qualsevol congruència mòdul està formada, tal 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 al producte, només es tractarà amb els elements que sí que en tenen.

Amb aquest darrer apunt apareix una nova pregunta: com se sap quins elements, donada una congruència módul, tenen inversa dins aquesta? Que un element sigui inversa d'un altre es denota matemàticament amb la següent sentència: y invers de x : $\iff y*x=e$ , on e és l'element neutre respecte al producte. Per tant en aquest cas, donat que a $(\mathbb {Z} _{n},+,*)$ l'element neutre és l'1, l'element invers d'una x qualsevol pertanyent a la congruència mòdul serà aquell element que dugui el mòdul del producte a la unitat. Un exemple això és: $x*3=1mod(7)=5*3=15mod(7)=1mod(7)$

Per tant l'invers del 3 en la congruència mòdul d'índex 7 és el 5. La pregunta que abans s'ha formulat és però com saber si un element té inversa, i és que no tots els elements de $(\mathbb {Z} _{n},+,*)$ tindran inversa. Analíticament, trobar el "representant" de qualsevol nombre natural segons la relació d'equivalència serà senzillament fer la divisió sencera del nombre en qüestió entre l'índex de modulació i trobar, mitjançant aquest, el ròssec (vegeu l'exemple anterior); per tant trobar la inversa d'un nombre de l'anell serà senzillament trobar aquell nombre tal que, multiplicat per l'element de qui volem trobar la inversa, doni de mòdul la unitat, això però no sempre serà possible. Efectivament, si un nombre no és coprimer amb l'índex de modulació, això és no tenir en comú cap nombre primer comú amb l'índex n de la congruència mòdul, serà impossible trobar-li cap inversa:

x*y=x*\prod _{i=1}^{k}p_{i}^{e_{i}}=K*\prod _{j=1}^{m}p_{j}^{e_{j}}+N

On N és el "representant" del producte de x*y. El cas és que, si es trasllada la y de l'esquerra a la dreta de la igualtat es pot treure factor comú al primer coincident i queda: $N=(x*\prod _{i=1}^{k}p_{i}^{e_{i}}-K*\prod _{j=1}^{m}p_{j}^{e_{j}})*\prod _{l=1}^{h}p_{l}^{e_{l}}$

Segons la quantitat de nombres primers coincidents (paràmetre determinat per h). Així doncs s'observa que N mai podrà prendre el valor 1 per estar lligat al conjunt de primers coincidents (a aquest resultat es pot arribar d'igual manera mitjançant l'algorisme d'Euclides estès). Per tant es determina que els únics nombres de la congruència mòdul $(\mathbb {Z} _{n},+,*)$ que tenen invers són aquells que no tenen cap primer coincident amb els primers que conformen l'índex de modulació n, és a dir, els que són coprimers amb n. I és en aquest punt on apareix de manera natural la funció Phi d'Euler, descrita matemàticament com: $\phi (n)=\prod _{i=1}^{k}p_{i}^{e_{i}-1}*(p_{i}-1)$ On p_i són els primers que conformen n amb llurs potències e_i. La pregunta obligada és què hi té a veure la funció Phi d'Euler amb la quantitat de nombres coprimers amb un donat n. Doncs resulta que la funció $\Phi$ (n) dona com a resultat justament aquesta xifra.

Funció Fi d'Euler

La funció Fi d'Euler, tal com s'ha descrit, es pot denotar matemàticament com: $\phi (n)=\prod _{i=1}^{k}p_{i}^{e_{i}-1}*(p_{i}-1)$

Aquesta funció compta 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_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 $\phi$ (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:

\phi '(n)=n-\sum _{i=1}^{k}a_{i}

Per trobar el límit superior del sumatori hem de conèixer la quantitat de primers que conformen n, ja que tindran valors coincidents. Aquesta expressió però no és encara el resultat desitjat, ja que resten per eliminar altres nombres que, no essent coprimers amb n, tenen primers que n no té. Per trobar aquests elements es procedeix a construir nombres a partir de primers pertanyents a n de la forma:

$m=\prod _{i=1}^{k}p_{i}^{e_{i}-1}*k$

De manera que aquest estigui per sota de n. El gran dubte està a saber quina quantitat de nombres d'aquesta mena menors de n hi haurà. Per a trobar aquest valor ens valem de la següent afirmació: donada una combinació de potències de primers com l'anterior, podrem trobar tants nombres que siguin coprimers amb n i menors que aquest com:

$C={\frac {n}{\prod _{i=1}^{k}p_{i}^{e_{i}-1}}}$

Aquest resultat és vàlid per a qualsevol combinació de primers, sempre que aquests pertanyin a la factorització de n. Efectivament veiem com la darrera sentència no és més que una generalització dels casos exposats més a dalt, per tant treballarem amb aquestes equacions i no pas amb les anteriors, que eren introductòries. Cal notar però, que és molt possible, i de fet així passa, que en el recompte de nombres coprimers amb n es comptin dues vegades un mateix nombre. Efectivament, fent servir el resultat C iterativament es tindrà en compte dues vegades el nombre:

$A_{1}=p_{1}*p_{2}*K$ i $A_{2}=p_{2}*p_{1}*K$

Així doncs haurem de sumar els nombres de la forma:

$C'={\frac {n}{p_{i}*p_{j}}}$

Ara es dona la situació inversa a l'anterior, hem afegit nombres que no hi haurien de ser degut a la darrera operació (vegeu càculs d'A₁ i A₂), concretament els nombres de la forma A₁=p₁*p₂*p₃*K i les seves combinacions, per tant li haurem de restar aquest cop la següent quantitat:

$C'={\frac {n}{p_{i}*p_{j}*p_{k}}}$

Fent anar aquest mètode iterativament al límit tindrem la següent quantitat:

$C=n-\sum _{i=1}^{m}{\frac {n}{p_{i}}}+\sum _{i=1,j=1}^{m}{\frac {n}{p_{i}*p_{j}}}-...=n*\sum _{i=0}^{m}{\frac {(-1)^{i}}{<\prod _{j=1}^{i}p_{i}>}}$

A on els clausors que envolten el productori expressen que s'agafa totes les possibles combinacions de p_i i p_j, tot obviant però les permutacions. Observant l'anterior expressió s'observa que aquesta no és altra cosa que un productori de binomis, de la forma:

$C=n*(1-{\frac {1}{p_{1}}})*(1-{\frac {1}{p_{2}}})*...*(1-{\frac {1}{p_{m}}})=n*\prod _{i=1}^{m}(1-{\frac {1}{p_{i}}}).$

I aquesta expressió és justament la funció Phi d'Euler:

$\phi (n)=\prod _{i=1}^{m}p_{i}^{e_{i}-1}*(p_{i}-1)QED$

Vegem tot això en un exemple pràctic. Imaginem que volem esbrinar quants nombres coprimers amb 36 hi ha entre 0 i aquest nombre. Apliquem el mètode que s'ha explicat: primer de tot restem de 36 tots els nombres múltiples dels primers de 36, tals com:

$A_{1}=2*k1$ i $A_{2}=3*k2$

A on encada cas, les k's podran arribar a prendre valors fins al següent límit:

$k1_{max}={\frac {36}{2}}$ i $k2_{max}={\frac {36}{3}}$

Tal 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:

$A_{1}'=2*3*k1'$ i $A_{2}'=3*2*k2'={6,12,24...}$

Per tant afegim a la fórmula els nombres que tinguin justament aquesta fórmula: A=2*3*k, la quantitat dels quals serà aquesta vegada:

$k_{max}={\frac {36}{2*3}}$

En resum la quantitat de nombres coprimers amb 36 i menors que aquest serà:

$\phi (36)=36-{\frac {36}{2}}-{\frac {36}{3}}+{\frac {36}{2*3}}=36*(1-{\frac {1}{2}})*(1-{\frac {1}{3}})=12$

I efectivament es comprova com la col·lecció de nombres naturals menors que 36 que són coprimers amb 36 són {1,5,7,11,13,17,19,23,25,29,31,35}, que són exactament 12 nombres.

Les principals propietats de la funció Phi d'Euler són:

Φ(p) = p - 1 si p és primer,
Φ(p^e) = p^e (1 - p^-1) si p és primer i e és un nombre natural, i
Φ(ab) = Φ(a)Φ(b) si mcd{a, b} = 1

La demostració d'aquestes propietats és immediata si es fa servir el mètode emprat en la demostració de la mateixa funció Phi.

Identitats que relacionen la funció Phi d'Euler amb altres funcions i identitats matemàtiques són les que segueixen:

$\sum _{d\mid n}\varphi (d)=n$
$\varphi (n)=\sum _{d\mid n}d\mu (n/d)$

A on la funció $\mu (n/d)$ é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, en 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 com ja s'ha dit, la funció Phi d'Euler dona 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 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, ${\frac {\phi (n)}{n}}$ ens descriurà la densitat la densitat de nombres primers.

Teorema d'Euler-Fermat

Tal 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:

a^{\Phi (n)}=1mod(n)

A on a és un nombre coprimer amb n i $\phi (n)$ és la funció d'Euler avaluada en n. Per arribar a aquest resultat primer s'han de conèixer els generadors de Z_n.

Generadors de l'anell $(\mathbb {Z} _{n},+,*)$

Es coneixen com a generadors d'un conjunt aquell element del mateix que és capaç d'expressar qualsevol altre mitjançant el següent morfisme:

$a^{r}=b,\forall a,b\in (\mathbb {Z} _{n},+,*),\forall r\in \mathbb {N}$

El concepte de generadors s'entén com aquell element de l'anell que, sota l'operador intern pertinent, pot generar qualsevol element del mateix anell com a resultat d'aplicar iterativament el dit operador intern sobre si mateix. Aquest concepte òbviament s'aplica sobre anells de conjunts finits, de tal manera que es pugui introduir el factor periòdic per a aplicar certes restriccions. Doncs, aplicant el concepte dels generadors al cas dels anells modulars, s'han de trobar els elements que ens puguin interessar per ser precísament generadors. Com que es tracta amb anells de conjunts extrets de conjunts qüocients, la relació d'equivalència que s'ha imposat a l'hora de crear-los dirà quins són els elements del conjunt que ens interessa: veiem-ne un exemple pràctic:

$2^{1}=2mod(5),2^{2}=4mod(5),2^{3}=3mod(5),2^{4}=1mod(5),2^{5}=2mod(5)...$

Com podem veure l'element de l'anell 2 ens genera una sèrie d'elements del mateix anell, per després repetir-se indefinidament, la pregunta en aquest cas serà: quants elements diferents ens generarà un cert element? Quins elements ens generarà? Hi haurà alguna relació entre generadors? Totes aquestes preguntes tenen una certa resposta dins el camp de les congruències modulars. Explícitament, un element que tingui inversa segons el producte habitual només podrà arribar a generar elements que al seu torne també tinguin inversa. Efectivament:

$a^{r}*b=1mod(n)\Rightarrow a^{r-1}*(a*b)=1mod(n)\Rightarrow ...\Rightarrow a*(a^{r-1}*b)=1mod(n)$

Per tant observem com se'ns genera una sèrie d'elements pertanyents a l'anell que tenen inversa, i de fet és un absurd suposar que <a> pugui generar un nombre que no tingui inversa, ja que per inducció s'arribaria a la conclusió de què a tampoc no en té. Aquest resultat diu tanmateix que qualsevol element amb inversa respecte al producte habitual generarà elements també invertibles, i dualment qualsevol element no invertible generarà elements no invertibles.

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'elements invertibles de l'anell $(\mathbb {Z} _{n},+,*)$ ; 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 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 com s'ha apuntat amb anterioritat la mida del conjunt generat serà precisament $\phi (n)$ , dit d'una altra manera:

$C(<a>)=\phi (n)$

A on C denota la cardinalitat del conjunt generat i $\phi (n)$ és la funció d'Euler. L'existència d'aquest element es desprèn del següent resultat: tots els integrants del conjunt d'elements invertibles tenen un semblant tal que el producte entre ambdós valors dona la unitat, per tant en l'espai generat hi ha d'haber un conjunt d'elements amb els seus inversos; ara bé, si no existís un element que generés la totalitat d'elements invertibles tindríem una sèrie de conjunts la intersecció dels quals seria el nombre '1', la qual cosa contradiu un dels principis que ha de complir com a conjunt: a*b $\in$ Z_n, més explícitament:

$a^{r_{1}}*b^{r_{2}}\in Z_{n}\Rightarrow a^{r_{1}}*b^{r_{2}}=c^{r}$

Aquesta expressió implica que, com que l'operador del producte recau sobre el conjunt, sempre s'ha de poder expressar el producte entre dos generadors amb un tercer generador. Si s'agafen tots els generadors i es multipliquen s'ha de continuar mantenint la condició:

$a_{1}^{r_{1}}*a_{2}^{r_{2}}*...*a_{m}^{r_{m}}\in Z_{n}\Rightarrow \prod _{i=1}^{m}a_{i}^{r_{i}}=b^{r}$

Mitjançant aquesta darrera expressió podem expressar doncs que almenys ha d'existir un element que pugui expressar qualsevol altre element com a potència d'ell mateix, aquest element l'anomenarem generador primari. Un cop demostrat aquest punt, es pot enunciar formalment un versió reduïda del teorema d'Euler-Fermat:

Ta d'Euler Fermat: Sigui una congruència modular (Z_n,+,*), existirà almenys un element invertible tal que es compleixi:

$a^{\phi (n)}=1mod(n)$

A on tal com ja s'ha dit abans $\phi (n)$ é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:

$b=a^{r}mod(n)\Rightarrow b^{r_{1}}=a^{r*r_{1}}mod(n),\forall r,r_{1}\in \mathbb {N}$

Per tant, donat un generador qualsevol, el seu conjunt estarà inscrit en el del generador primari, i la distància dins el conjunt del generador primari que guardaran els diversos elements del conjunt de l'altre generador la donarà la posició d'aquest. Veiem-ne un exemple: A la congruència mòdul Z₁₇ l'element 3 és un possible generador primari, ja que:

<3>={3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1}

<2>={3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1}

A on el conjunt de <2> està format només pels nombres en negreta. Així doncs, partint del fet que podem expressar qualsevol nombre pertanyent a l'òrbita de <2> com a potència del generador primari, arribem al resultat següent: la cardinalitat de qualsevol nombre invertible a valdrà:

$(g(a)*C(a))=0mod(\phi (n))$

A on g(a) és la posició de l'element a al conjunt del generador primari, C(a) és la cardinalitat a trobar i $\phi (n)$ és la funció d'Euler. Aquesta expressió ens dona quantes vegades hem desplaçar-nos pel conjunt del generador primari segons g(a) per arribar justament al '1'. Òbviament, aquest valor sempre serà múltiple de $\phi (n)$ . Un exemple d'això és: