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:

  01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16  17  18 19  20  21  22  23  24  25  1  1  2  2  4  2  6  4  6  4  10  4  12  6  8  8  16  6  18  8  12  10  22  8  20  26  27  28  29  30  31  32  33  34  35  36  37  38 39  40  41  42  43  44  45  46  47  48  49  50  12  18  12  28  8  30  16  20  16  24  12  36  18  24  16  40  12  42  20  24  22  46  16  42  20  51  52  53  54  55  56  57  58 59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  32  24  52  18  40  24  36  28  58  16  60  30  36  32  48  20  66  32  44  24  70  24  72  36  40  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  36  60  24  78  32  54  40  82  24  64  42  56  40  88  24  72  44  60  46  72  32  96  42  60  40

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.

Kategori:Tallteori
Kategori:Algebra