Indicator (getaltheorie)

In de getaltheorie is de indicator of totiënt van een positief natuurlijk getal $n$, genoteerd als $\phi (n)$, het aantal positieve natuurlijke getallen kleiner dan of gelijk aan $n$ die onderling ondeelbaar zijn met $n$. Zo is bijvoorbeeld $\phi (8)=4$, omdat van elk van de vier oneven getallen 1, 3, 5 en 7 de grootste gemene deler met 8 gelijk is aan 1, en die vier getallen daarom onderling ondeelbaar met 8 zijn. De indicator wordt veelal in verband gebracht met de Zwitserse wiskundige Leonhard Euler, die deze functie uitgebreid bestudeerde.

Definitie

De indicator of totiënt $\phi (n)$ van een natuurlijk getal $n\ne 0$ is het aantal positieve natuurlijke getallen kleiner dan of gelijk aan $n$ die relatief priem zijn met $n$.

$\phi (n)=\mathrm{\#}\{m\in \mathbb{N}\mid 1\le m\le n,\mathrm{ggd}(m,n)=1\}$

Voorbeelden

Voor een priemgetal $p$ is $\phi (p)=p-1$, omdat alle gehele getallen $k,1\le k<p$ geen deler met $p$ gemeen hebben. Zo is $\phi (2)=1$. Alle overige priemgetallen zijn oneven, zodat $\phi (p)$ een even getal is.

Voor het getal 12 geldt dat 1, 5, 7 en 11 geen gemene deler met 12 hebben. Dus is $\phi (12)=4$.

Eigenschappen

• De stelling van Euler zegt dat als $a$ onderling ondeelbaar is met $n$, dat wil zeggen $\mathrm{g}\mathrm{g}\mathrm{d}(a,n)=1$, dan is

$a^{\phi (n)}=1modn$

• De indicator geeft ook de omvang aan van de multiplicatieve groep van omkeerbare natuurlijke getallen modulo $n$. Meer precies is $\phi (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.

• Het getal $\phi (n)$ is ook gelijk aan het aantal generators van de cyclische groep $C_n$. Omdat ieder element van $C_n$ een cyclische deelgroep genereert en de deelgroepen van $C_n$ van de vorm $C_d$ zijn waarin $d$ deler is van $n$ (geschreven als $d|n$), geldt:

$\sum _{d\mid n}\phi (d)=n$

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

• Met behulp van de möbius-inversieformule kan deze som omgedraaid worden om een andere formule te krijgen voor $\phi (n)$

$\phi (n)=\sum _{d|n}d\cdot \mu (n/d)$,

waarin $\mu$ de möbiusfunctie is.

• De indicator is een multiplicatieve rekenkundige functie. Er geldt voor $m$ en $n$ die relatief priem zijn:

$\phi (mn)=\phi (m)\phi (n)$

Bijvoorbeeld is $\phi (36)=12=2\times 6=\phi (4)\phi (9)$.

(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\times B$ en $C$ via de Chinese reststelling.)

Berekening van de indicator

Uit de definitie volgt dat $\phi (1)=1$ en $\phi (p)=p-1$ als $p$ een priemgetal is. Voor een natuurlijke exponent $k\ge 2$ geldt dat de getallen tussen 1 en $p^k$ die een priemfactor (noodzakelijk $p$) gemeen hebben met $p^k,$ precies de veelvouden zijn van $p.$ Het aantal van die veelvouden is $p^{k-1},$ zodat $\phi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$

Omdat $\phi$ een multiplicatieve functie is kan de waarde van $\phi (n)$ berekend worden met de hoofdstelling van de rekenkunde. Als

$n=p_1^{k_1}\cdot \dots \cdot p_r^{k_r}$

waarin de $p_j$ verschillende priemgetallen zijn, dan is

$\phi (n)=p_1^{k_1-1}(p_1-1)\cdot \dots \cdot p_r^{k_r-1}(p_r-1)$

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

$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})$

met het product over alle priemgetallen $p$ die deler zijn van $n$.

Voortbrengende functies

Een dirichlet-reeks met $\phi (n)$ is

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)}{n^s}=\frac{\zeta (s-1)}{\zeta (s)}$

Een lambert-rij voortbrengende functie is

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\frac{q}{(1-q{)}^2}$,

geldig voor alle $|q|<1$.

Groei van de functie

De groei van $\phi (n)$ als een functie van $n$ is een interessante vraag, omdat de eerste indruk dat $\phi (n)$ bij een kleine $n$ veel kleiner is dan $n$ ietwat misleidend is. Asymptotisch geldt dat bij iedere $\epsilon >0$ een $N(\epsilon )$ bestaat, zodanig dat voor $n>N(\epsilon )$ geldt:

$n^{1-\epsilon }<\phi (n)<n$

Er geldt:

$\frac{\phi (n)}{n}=\prod _{p|n}(1-\frac{1}{p})$

dus het product over de priemgetallen $p$ die $n$ delen. Uit de priemgetalstelling kan aangetoond worden dat voor constante $\epsilon$ dit vervangen kan worden door

$\frac{C\log \log n}{\log n}$

Dit is ook waar in het gemiddelde:

$\frac{1}{n^2}\sum _{k=1}^n\phi (k)=\frac{3}{{\pi }^2}+𝒪\left(\frac{\ln n}{n}\right)$

waarin de grote O een landau-symbool is.

Enkele functiewaarden

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

Overige

• Een niettotiënt is een positief natuurlijk getal $n$ waarvoor er geen groter getal $x$ dan $n$ bestaat, zodat de indicator $\phi (x)=n$.
• De stelling van Gauss-Wantzel zegt dat een regelmatige $n$-hoek dan en slechts dan met passer en liniaal kan worden getekend als $\phi (n)$ een macht van 2 is. Dat is bijvoorbeeld het geval voor de regelmatige vijfhoek en de regelmatige zeshoek, maar niet voor de zevenhoek omdat $\phi (7)=6$.

Literatuur

• Sjabloon:En Sjabloon:Aut en Sjabloon:Aut. Handbook of Mathematical Functions, 1964. paragraaf 24.3.2. ISBN 0-486-61272-4
• Sjabloon:Aut Inleiding tot de Algebra, vijfde druk, Wolters-Noordhoff, Groningen, 1972, blz. 38. ISBN 90-01-55151-3