# 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

| 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