Indicator (getaltheorie)

In de getaltheorie is de indicator of totiënt^[1] 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 vaak in verband gebracht met de Zwitserse wiskundige Leonhard Euler, die deze functie uitgebreid heeft bestudeerd.

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 met ${\displaystyle n}$ onderling ondeelbaar zijn.

${\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}$ en ${\displaystyle n}$ onderling ondeelbaar zijn, dat wil zeggen ${\displaystyle \mathrm {ggd} (a,n)=1}$, dan

${\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 ondergroep, 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 ondergroep genereert en de ondergroepen van ${\displaystyle C_{n}}$ van de vorm ${\displaystyle C_{d}}$ zijn waarin ${\displaystyle n}$ door ${\displaystyle d}$ kan worden gedeeld, 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 worden omgedraaid om een andere formule voor ${\displaystyle \varphi (n)}$ te krijgen

${\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}$, dan is er via de Chinese reststelling een bijectie tussen ${\displaystyle A\times B}$ en ${\displaystyle C}$.

Berekening van de indicator

Het volgt uit de definitie 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 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)}$ met de hoofdstelling van de rekenkunde worden berekend. 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 dirichletreeks 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

Grafiek van de eerste 100 waarden van de eulerfunctie. De waarden op de bovenste lijn behoren bij de priemgetallen

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 worden aangetoond dat voor constante ${\displaystyle \varepsilon }$ dit kan worden vervangen 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 ${\displaystyle {\mathcal {O}}}$ een grote-O-notatie 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