Indicator (getaltheorie)

getaltheorie

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

DefinitieBewerken

De indicator of totiënt   van een natuurlijk getal   is het aantal positieve natuurlijke getallen kleiner dan of gelijk aan   die relatief priem zijn met  .

 

VoorbeeldenBewerken

Voor een priemgetal   is  , omdat alle gehele getallen   geen deler met   gemeen hebben. Zo is  . Alle overige priemgetallen zijn oneven, zodat   een even getal is.

Voor het getal 12 geldt dat 1, 5, 7 en 11 geen gemene deler met 12 hebben. Dus is  .

EigenschappenBewerken

  • De stelling van Euler zegt dat als   onderling ondeelbaar is met  , dat wil zeggen  , dan is
 
  • De indicator geeft ook de omvang aan van de multiplicatieve groep van omkeerbare natuurlijke getallen modulo  . Meer precies is   de orde van de vermenigvuldigingsgroep van de omkeerbare elementen in de ring  . Dit feit, samen met de stelling van Lagrange over de orde van een deelgroep, geeft een bewijs voor de stelling van Euler.
  • Het getal   is ook gelijk aan het aantal generators van de cyclische groep  . Omdat ieder element van   een cyclische deelgroep genereert en de deelgroepen van   van de vorm   zijn waarin   deler is van   (geschreven als  ), geldt:
 
waarin de som zich uitstrekt over alle positieve delers   van  .
  • Met behulp van de möbius-inversieformule kan deze som omgedraaid worden om een andere formule te krijgen voor  
 ,
waarin   de möbiusfunctie is.
  • De indicator is een multiplicatieve rekenkundige functie. Er geldt voor   en   die relatief priem zijn:
 
Bijvoorbeeld is  .
(Schets van het bewijs: Zij   de verzameling residuklassen modulo-en-onderling-ondeelbaar-tot   respectievelijk; dan is er een bijectie tussen   en   via de Chinese reststelling.)

Berekening van de indicatorBewerken

Uit de definitie volgt dat   en   als   een priemgetal is. Voor een natuurlijke exponent   geldt dat de getallen tussen 1 en   die een priemfactor (noodzakelijk  ) gemeen hebben met   precies de veelvouden zijn van   Het aantal van die veelvouden is   zodat  

Omdat   een multiplicatieve functie is kan de waarde van   berekend worden met de hoofdstelling van de rekenkunde. Als

 

waarin de   verschillende priemgetallen zijn, dan is

 

Deze laatste formule is een euler-product en wordt meestal geschreven als

 

met het product over alle priemgetallen   die deler zijn van  .

Voortbrengende functiesBewerken

Een dirichlet-reeks met   is

 

Een lambert-rij voortbrengende functie is

 ,

geldig voor alle  .

Groei van de functieBewerken

De groei van   als een functie van   is een interessante vraag, omdat de eerste indruk dat   bij een kleine   veel kleiner is dan   ietwat misleidend is. Asymptotisch geldt dat bij iedere   een   bestaat, zodanig dat voor   geldt:

 

Er geldt:

 

dus het product over de priemgetallen   die   delen. Uit de priemgetalstelling kan aangetoond worden dat voor constante   dit vervangen kan worden door

 

Dit is ook waar in het gemiddelde:

 

waarin de grote O een landau-symbool is.

Enkele functiewaardenBewerken

 
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

OverigeBewerken

LiteratuurBewerken