Indicator (getaltheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de getaltheorie is de indicator of totiënt van een positief natuurlijk getal n, genoteerd als φ(n), het aantal positieve natuurlijke getallen kleiner dan of gelijk aan n die onderling ondeelbaar zijn met n. Zo is φ(8) = 4, omdat de vier getallen 1, 3, 5 en 7 geen grootste gemene deler hebben met 8 (behalve 1) en daarom onderling ondeelbaar met 8 worden genoemd. Als n een priemgetal is, dan is φ(n) gelijk aan n-1.

De indicator wordt veelal in verband gebracht met de Zwitserse wiskundige Leonhard Euler, die deze functie uitgebreid bestudeerde.

De indicator geeft ook de omvang aan van de multiplicatieve groep van natuurlijke getallen modulo n. Meer precies is φ(n) de orde van de vermenigvuldigingsgroep van de omkeerbare elementen in de ring \mathbb{Z}/n\mathbb{Z}. Dit feit, samen met de stelling van Lagrange over de orde van een deelgroep, geeft een bewijs voor de stelling van Euler.

Berekening van de indicator[bewerken]

Uit de definitie volgt dat φ(1) = 1, en φ(n) is (p-1)pk-1 als n de kde macht van een priemgetal pk is. Bovendien is φ een multiplicatieve functie; als m en n onderling ondeelbaar zijn, dan is φ(mn) = φ(m)φ(n). (Schets van het bewijs: Zij A, B, C de verzameling residuklassen modulo-en-onderling-ondeelbaar-tot m, n, mn respectievelijk; dan is er een bijectie tussen A×B en C, via de Chinese reststelling.) De waarde van φ(n) kan dus berekend worden met de hoofdstelling van de rekenkunde: als

n = p1k1 ... prkr

waarin de pj verschillende priemgetallen zijn, dan

φ(n) = (p1−1) p1k1−1 ... (pr−1) prkr−1.

Deze laatste formule is een euler-product en wordt meestal geschreven als

\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)

met het product over alle verschillende priemgetallen pr.

Andere eigenschappen[bewerken]

Het getal φ(n) is ook gelijk aan het aantal generators van de cyclische groep Cn. Omdat ieder element van Cn een cyclische deelgroep genereert en de deelgroepen van Cn van de vorm Cd zijn waarin d deelt n (geschreven als d|n), krijgen we

\sum_{d\mid n}\varphi(d)=n

waarin de som zich uitstrekt over alle positieve delers d van n.

We gebruiken nu de Möbius-inversieformule om deze som om te draaien en een andere formule te krijgen voor φ(n)

\varphi(n)=\sum_{d\mid n} d \mu(n/d)

waarin \mu de gebruikelijke möbiusfunctie gedefinieerd over de positieve natuurlijke getallen.

Als a onderling ondeelbaar is met n, of, ggd(a,n)=1 dan

a^{\varphi(n)}=1\mod n.

Voortbrengende functies[bewerken]

Een Dirichlet-reeks met φ(n) is

\sum_{n=1}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

Een Lambert-rij voortbrengende functie is

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

welke waar is voor alle |q|<1.

Groei van de functie[bewerken]

De groei van φ(n) als een functie van n is een interessante vraag, omdat de eerste indruk dat bij een kleine n φ(n) veel kleiner is dan n ietwat misleidend is. Asymptotisch hebben we

n1−ε < φ(n) < n

voor iedere ε > 0 en n > N(ε). Als we beschouwen:

φ(n)/n

kunnen we dat schrijven, vanuit bovenstaande formule, als het product van factoren

1 −p−1

over de priemgetallen p die n delen. Uit de priemgetalstelling kan aangetoond worden dat voor constante ε dit vervangen kan worden door

C loglog n/log n.

Dit is ook waar in het gemiddelde:

\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\ln n }{n}\right)

waarin de grote O een Landau-symbool is.

Enkele functiewaarden[bewerken]

Grafiek van de eerste 100 waarden van de Eulerfunctie. De waarden op de bovenste lijn behoren bij de priemgetallen.
n φ(n) n φ(n) n φ(n) n φ(n) n φ(n) n φ(n) n φ(n) n φ(n)
1 1 11 10 21 12 31 30 41 40 51 32 61 60 71 70
2 1 12 4 22 10 32 16 42 12 52 24 62 30 72 24
3 2 13 12 23 22 33 20 43 42 53 52 63 36 73 72
4 2 14 6 24 8 34 16 44 20 54 18 64 32 74 36
5 4 15 8 25 20 35 24 45 24 55 40 65 48 75 40
6 2 16 8 26 12 36 12 46 22 56 24 66 20 76 36
7 6 17 16 27 18 37 36 47 46 57 36 67 66 77 60
8 4 18 6 28 12 38 18 48 16 58 28 68 32 78 24
9 6 19 18 29 28 39 24 49 42 59 58 69 44 79 78
10 4 20 8 30 8 40 16 50 20 60 16 70 24 80 32

Zie ook[bewerken]

Referenties[bewerken]