Indicator (getaltheorie)

In de getaltheorie is de indicator of totiënt van een positief natuurlijk getal $n$, genoteerd als $\varphi (n)$, het aantal positieve natuurlijke getallen kleiner dan of gelijk aan $n$ die onderling ondeelbaar zijn met $n$. Zo is bijvoorbeeld $\varphi (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 $\varphi (n)$ van een natuurlijk getal $n\neq 0$ is het aantal positieve natuurlijke getallen kleiner dan of gelijk aan $n$ die relatief priem zijn met $n$.

$\varphi (n)=\#\{m\in \mathbb {N} \mid 1\leq m\leq n,\operatorname {ggd} (m,n)=1\}$

Voorbeelden

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

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

Eigenschappen

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

$a^{\varphi (n)}=1{\bmod {n}}$

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

$\varphi (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:

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

Bijvoorbeeld is $\varphi (36)=12=2\times 6=\varphi (4)\varphi (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 $\varphi (1)=1$ en $\varphi (p)=p-1$ als $p$ een priemgetal is. Voor een natuurlijke exponent $k\geq 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 $\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1).$

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

$n=p_{1}^{k_{1}}\cdot \ldots \cdot p_{r}^{k_{r}}$

waarin de $p_{j}$ verschillende priemgetallen zijn, dan is

$\varphi (n)=p_{1}^{k_{1}-1}(p_{1}-1)\cdot \ldots \cdot p_{r}^{k_{r}-1}(p_{r}-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 priemgetallen $p$ die deler zijn van $n$.

Voortbrengende functies

Een dirichlet-reeks met $\varphi (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}}}$,

geldig voor alle $|q|<1$.

Groei van de functie

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

$n^{1-\varepsilon }<\varphi (n)<n$

Er geldt:

${\frac {\varphi (n)}{n}}=\prod _{p|n}\left(1-{\frac {1}{p}}\right)$

dus het product over de priemgetallen $p$ die $n$ delen. Uit de priemgetalstelling kan aangetoond worden dat voor constante $\varepsilon$ 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}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\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 $\varphi (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 $\varphi (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 $\varphi (7)=6$.

Literatuur

• (en) Milton Abramowitz en Irene A. Stegun. Handbook of Mathematical Functions, 1964. paragraaf 24.3.2. ISBN 0-486-61272-4
• F. Loonstra Inleiding tot de Algebra, vijfde druk, Wolters-Noordhoff, Groningen, 1972, blz. 38. ISBN 90-01-55151-3