Eulers totientfunksjon

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

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[rediger | rediger kilde]

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

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[rediger | rediger kilde]

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 φ(72) = φ(23)⋅φ(32) = 72/3 = 24. 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[rediger | rediger kilde]

  • O. Ore, Number Theory and Its History, Dover Publications Inc., New York (1988). ISBN 0-486-65620-9.

Eksterne lenker[rediger | rediger kilde]