Indicator (getaltheorie)

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

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

Voorbeelden

Voor een priemgetal ${\displaystyle p}$ is ${\displaystyle \varphi (p)=p-1}$, omdat alle gehele getallen ${\displaystyle k,\ 1\leq k<p}$ geen deler met ${\displaystyle p}$ gemeen hebben. Zo is ${\displaystyle \varphi (2)=1}$. Alle overige priemgetallen zijn oneven, zodat ${\displaystyle \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 ${\displaystyle \varphi (12)=4}$.

Eigenschappen

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

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

• De indicator geeft ook de omvang aan van de multiplicatieve groep van omkeerbare natuurlijke getallen modulo ${\displaystyle n}$. Meer precies is ${\displaystyle \varphi (n)}$ de orde van de vermenigvuldigingsgroep van de omkeerbare elementen in de ring ${\displaystyle \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 ${\displaystyle \varphi (n)}$ is ook gelijk aan het aantal generators van de cyclische groep ${\displaystyle C_{n}}$. Omdat ieder element van ${\displaystyle C_{n}}$ een cyclische deelgroep genereert en de deelgroepen van ${\displaystyle C_{n}}$ van de vorm ${\displaystyle C_{d}}$ zijn waarin ${\displaystyle d}$ deler is van ${\displaystyle n}$ (geschreven als ${\displaystyle d|n}$), geldt:

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

waarin de som zich uitstrekt over alle positieve delers ${\displaystyle d}$ van ${\displaystyle n}$.

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

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

waarin ${\displaystyle \mu }$ de möbiusfunctie is.

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

${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$

Bijvoorbeeld is ${\displaystyle \varphi (36)=12=2\times 6=\varphi (4)\varphi (9)}$.

(Schets van het bewijs: Zij ${\displaystyle A,B,C}$ de verzameling residuklassen modulo-en-onderling-ondeelbaar-tot ${\displaystyle m,n,mn}$ respectievelijk; dan is er een bijectie tussen ${\displaystyle A\times B}$ en ${\displaystyle C}$ via de Chinese reststelling.)

Berekening van de indicator

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

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

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

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

${\displaystyle \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

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

met het product over alle priemgetallen ${\displaystyle p}$ die deler zijn van ${\displaystyle n}$.

Voortbrengende functies

Een dirichlet-reeks met ${\displaystyle \varphi (n)}$ is

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

Een lambert-rij voortbrengende functie is

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

geldig voor alle ${\displaystyle |q|<1}$.

Groei van de functie

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

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

Er geldt:

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

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

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

Dit is ook waar in het gemiddelde:

${\displaystyle {\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

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 ${\displaystyle n}$ waarvoor er geen groter getal ${\displaystyle x}$ dan ${\displaystyle n}$ bestaat, zodat de indicator ${\displaystyle \varphi (x)=n}$.
• De stelling van Gauss-Wantzel zegt dat een regelmatige ${\displaystyle n}$-hoek dan en slechts dan met passer en liniaal kan worden getekend als ${\displaystyle \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 ${\displaystyle \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