Eulers totientfunksjon
From Wikipedia, the free encyclopedia
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.