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 = p^k  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, ..., p^{k − 1}p = p^k  ikke primiske med n. Det er i alt p^{k − 1}  av disse. Resten n - p^{k − 1}  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 φ(p) = p - 1. For eksempel er φ(32) = φ(2⁵) = 2⁵ - 2⁴ = 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=\prod _{p\mid n}p^{e_{p}}$

hvor eksponentene e_p 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 φ(72) = φ(2³)⋅φ(3²) = 72/3 = 24. For de første 100 heltallene finner man på denne måten:

$n$ 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 $\phi (n)$ 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

$n$ 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 $\phi (n)$ 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

$n$ 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 $\phi (n)$ 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

$n$ 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 $\phi (n)$ 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.