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 &phi;(*n*) og kalles derfor også for **Eulers &phi;-funksjon**. Som eksempel er &phi;(3) = 2 da både 1 og 2 er relativt primiske med 3. Likedan er &phi;(4) = 2 = &phi;(6), mens &phi;(8) = 4 da 1,3,5 og 7 er primiske relativt til 8. For et primtall *p* er &phi;(*p*) = *p* - 1 fordi alle tallene mindre enn *p* er relativt primiske. Som eksempel er &phi;(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 &phi;-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 &phi; 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 &phi;(*p*) = *p* - 1. For *p* = 2 gir dette &phi;(2) = 1 som er et odde tall. Det har sammenheng med at 2 er det eneste like primtall. For konsistens må man definere &phi;(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* = *p**k*&thinsp; hvor *p* er et primtall. De tallene som er mindre og deler *n*, må være et multiplum av *p*. Derfor er tallene &thinsp; ikke primiske med *n*. Det er i alt   av disse. Resten    er derfor relativt primiske med *n* slik at

:\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 &phi;(*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

: n = \prod_{p\mid n} p^{e_p}  

hvor eksponentene *e<sub>p</sub>* er karakteristiske for tallet *n*. Da de forskjellige faktorene her er relativt primiske, følger da fra resultatet over at

: \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  =  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.