Indicator (getaltheorie)

In de getaltheorie is de indicator of totient 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 onderling ondeelbaar zijn met 8.

De indicator wordt veelal in verband gebracht met de Zwitserse wiskundige Leonhard Euler, die de 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 groep van eenheid van de ring . Dit feit, samen met stelling van Lagrange, geeft een bewijs voor Stelling van Euler.

Inhoud 1 Berekening van de indicator 2 Andere eigenschappen 3 Genererende functies 4 Groei van de functie 5 Enkele functiewaarden 6 Zie ook 7 Referenties

[bewerk] Berekening van de indicator

Uit de definitie volgt dat φ(1) = 1, en φ(n) is (p-1)p^k-1 als n de kde macht van een priemgetal p^k 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 residu klassen modulo-en-onderling-ondeelbaar-tot m, n, mn respectievelijk; dan is er een bijectie tussen AxB en C, via de Chinese reststelling.) De waarde van φ(n) kan dus berekend worden met het fundamentele theorema van de rekenkunde: als

n = p₁^k₁ ... p_r^k_r

waarin de p_j verschillende priemgetallen zijn, dan

φ(n) = (p₁−1) p₁^k₁−1 ... (p_r−1) p_r^k_r−1.

Deze laatste formule is een Euler product en wordt meestal geschreven als

met het product over alle verschillende priemgetallen p_r.

[bewerk] Andere eigenschappen

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

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

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

waarin μ de gebruikelijke Möbius functie gedefinieerd over de positieve natuurlijke getallen.

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

.

[bewerk] Genererende functies

Een Dirichlet reeks met φ(n) is

Een Lambert rij genererende functie is

welke waar is voor alle |q|<1.

[bewerk] Groei van de functie

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

n^1−ε < φ(n) < n

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

φ(n)/n

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

1 −p⁻¹

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

C loglog n/log n.

Dit is ook waar in het gemiddelde:

waarin de grote O een Landau symbool is.

[bewerk] Enkele functiewaarden

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8

n	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
φ(n)	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12	36	18	24	16

n	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
φ(n)	40	12	42	20	24	22	46	16	42	20	32	24	52	18	40	24	36	28	58	16

n	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
φ(n)	60	30	36	32	48	20	66	32	44	24	70	24	72	36	40	36	60	24	78	32

[bewerk] Zie ook

• Niettotient
• Nietcototient
• Hogelijk totient getal
• Hogelijk cototient getal

[bewerk] Referenties

• Milton Abramowitz en Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications, New York. ISBN 486-61272-4 . See paragraph 24.3.2.