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 φ(m)⋅φ(n) = φ(mn). For eksempel, φ(42) = φ(6)⋅φ(7) = 2⋅6 = 12. 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 p, 2p, 3p, ..., pk − 1p = pk  ikke primiske med n. Det er i alt  pk − 1  av disse. Resten  n -  pk − 1   er derfor relativt primiske med n slik at

  
    
      
        ϕ
        (
        
          p
          
            k
          
        
        )
        =
        
          p
          
            k
          
        
        −
        
          p
          
            k
            −
            1
          
        
        =
        
          p
          
            k
          
        
        
          (
          
            1
            −
            
              
                1
                p
              
            
          
          )
        
        .
      
    
    {\displaystyle \phi (p^{k})=p^{k}-p^{k-1}=p^{k}\left(1-{\frac {1}{p}}\right).}
  som gjelder når p > 1.  Når k = 1, gir den som forventet φ(p) = p - 1.  For eksempel er φ(32) = φ(25) = 25 - 24 = 16. 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

  
    
      
        n
        =
        
          ∏
          
            p
            ∣
            n
          
        
        
          p
          
            
              e
              
                p
              
            
          
        
      
    
    {\displaystyle n=\prod _{p\mid n}p^{e_{p}}}
  hvor eksponentene ep er karakteristiske for tallet n. Da de forskjellige faktorene her er relativt primiske, følger da fra resultatet over at

  
    
      
        ϕ
        (
        n
        )
        =
        
          ∏
          
            p
            ∣
            n
          
        
        
          p
          
            
              e
              
                p
              
            
            −
            1
          
        
        (
        p
        −
        1
        )
        =
        n
        
          ∏
          
            p
            ∣
            n
          
        
        
          (
          
            1
            −
            
              
                1
                p
              
            
          
          )
        
      
    
    {\displaystyle \phi (n)=\prod _{p\mid n}p^{e_{p}-1}(p-1)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}
  .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 φ(72)  = φ(23)⋅φ(32) = 72/3 = 24. 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.