Eulers totientfunksjon

Eulers totientfunksjon er en aritmetisk funksjon som for hvert heltall n teller opp hvor mange postive heltall mindre enn n som er relativt primisk med n. Den betegnes vanligvis med symbolet φ(n) og kalles derfor også for Eulers φ-funksjon. Som eksempel er φ(3) = 2 da både 1 og 2 er relativt primiske med 3. Likedan er φ(4) = 2 = φ(6), mens φ(8) = 4 da 1,3,5 og 7 er primiske relativt til 8. For et primtall p er φ(p) = p - 1 fordi alle tallene mindre enn p er relativt primiske. Som eksempel er φ(7) = 6. Funksjonen kan beregnes direkte for alle tall som har en kjent primtallsfaktorering. Når n > 2 gir den bare like tall som resultat.  I dag spiller Eulers φ-funksjon en viktig rolle i moderne kryptografi.

Den sveitsiske matematiker Leonhard Euler har fått sitt navn knyttet til funksjonen som han var den første til å studere og gjøre bruk av på midten av 1700-tallet. Resten av navnet er forbundet med det latinske ordet tot som betyr helt eller alt og som opptrer i f.eks. in toto. Den greske bokstaven φ ble knyttet til funksjonen av den tyske matematiker Carl Friedrich Gauss noen tiår senere.

Viktige egenskaper

Tall k som er relativt primiske til et tall n, har en største felles divisor gcd(n,k) = 1. Er n lik med et primtall p, er alle positive heltall k < p relativt primiske med p, det vil si tallene k = 1,2,3,..., p - 1. Derfor er i dette tilfellet φ(p) = p - 1. For p = 2 gir dette φ(2) = 1 som er et odde tall. Det har sammenheng med at 2 er det eneste like primtall. For konsistens må man definere φ(1) = 1 som betyr at 1 er relativt primisk med seg selv og følger fra gcd(1,1) = 1. 

To relativt primiske heltall m og n har ingen felles faktorer. Derfor gjelder for disse  For eksempel,  =  For produkter som involverer de samme faktorene, er beregningen litt mer omstendelig.

Det enkleste tilfellet er når n = pk  hvor p er et primtall. De tallene som er mindre og deler n, må være et multiplum av p. Derfor er tallene   ikke primiske med n. Det er i alt   av disse. Resten    er derfor relativt primiske med n slik at

som gjelder når p > 1.  Når k = 1, gir den som forventet φ(p) = p - 1.  For eksempel er  =  Dermed kan funksjonsverdier beregnes for alle sammensatte tall.

Generell beregning

Ifølge aritmetikkens fundamentalteorem kan alle heltall n  faktoreres i potenser av hvert primtall p som deler det. Derfor er

 

hvor eksponentene ep er karakteristiske for tallet n. Da de forskjellige faktorene her er relativt primiske, følger da fra resultatet over at

 .

Dette er en generelt anvendbar formel for alle tall som har en kjent faktorisering. Formelen går tilbake til Euler. Den gir, for eksempel at  =  For de første 100 heltallene finner man på denne måten:

Litteratur
 O. Ore, Number Theory and Its History, Dover Publications Inc., New York (1988). ISBN 0-486-65620-9.

Eksterne lenker

 E.W. Weisstein, Totient function, Wolfram MathWorld.

Tallteori
Algebra