De Euler-phi functie

De Euler-phi functie, ook wel totiënt functie of indicator genoemd, telt het aantal positieve natuurlijke getallen kleiner dan of gelijk aan n, die onderling ondeelbaar zijn met n. Notatie: \varphi(n).

Zo is bijvoorbeeld \varphi(10)=4, want de enige getallen die onderling ondeelbaar zijn met 10 en kleiner zijn dan 10, zijn 1,3,7 en 9.

Enkele eigenschappen:

  • \varphi(1)=1.
  • Als p een priemgetal is dan is \varphi(p)=p-1.
  • Als p een priemgetal is dan is \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).
  • Als n=p_1^{k_1}.p_2^{k_2}.\cdots.p_r^{k_r} de priemontbinding is van n, dan geldt \varphi(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1). Dit kan je ook schrijven als :

        \[\varphi(n)= n.\prod_{p|n}(1-\frac{1}{p})\]

    Hierbij doorloopt p alle priemdelers van n.

  • \sum_{d|n}\varphi(d)=n
  • De indicator geeft ook de omvang aan van de multiplicatieve groep van natuurlijke getallen modulo n