Der Totient einer Zahl ist definiert als , welche auch Eulersche Phi-Funktion genannt wird und angibt, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind.

In der Zahlentheorie ist eine hochtotiente Zahl (vom englischen highly totient number) eine natürliche Zahl , für welche die Gleichung

mehr Lösungen hat als die Gleichung für jede andere natürliche Zahl .

Eine hochtotiente Zahl, welche Primzahl ist, nennt man hochtotiente Primzahl. Die einzige hochtotiente Primzahl ist .

Beispiele

Bearbeiten
  • Die Totienten  , also die Anzahl der zu   teilerfremden natürlichen Zahlen  , lauten (für  ):
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, … (Folge A000010 in OEIS)
Beispiel:
An der 8. Stelle obiger Liste steht die Zahl  . Die Zahl   hat   teilerfremde Zahlen, welche kleiner als   sind, nämlich   und  . Daher ist tatsächlich  .
An der 7. Stelle obiger Liste steht die Zahl  . Die Zahl   ist eine Primzahl und hat somit   teilerfremde Zahlen, welche kleiner als   sind, nämlich alle Zahlen von   bis  . Somit ist  .
  • Eine Primzahl   ist nur durch   und sich selbst teilbar. Somit ist sie zu den Zahlen   bis   teilerfremd. Also ist   (siehe Berechnung der Eulerschen Phi-Funktion). Somit gilt:
 
Der Totient jeder Primzahl   ist somit gleich  .
  • Sei  . Es gibt fünf Lösungen der Gleichung  , nämlich  ,  ,  ,   und  :
Die Zahl   ist zu den Zahlen   und   teilerfremd, es gibt also acht zu   teilerfremde Zahlen und es ist deswegen  . Der Totient der Zahl   ist also  .
Die Zahl   ist zu den Zahlen   und   teilerfremd, es gibt also acht zu   teilerfremde Zahlen und es ist deswegen  . Der Totient der Zahl   ist also  .
Die Zahl   ist zu den Zahlen   und   teilerfremd, es gibt also acht zu   teilerfremde Zahlen und es ist deswegen  . Der Totient der Zahl   ist also  .
Die Zahl   ist zu den Zahlen   und   teilerfremd, es gibt also acht zu   teilerfremde Zahlen und es ist deswegen  . Der Totient der Zahl   ist also  .
Die Zahl   ist zu den Zahlen   und   teilerfremd, es gibt also acht zu   teilerfremde Zahlen und es ist deswegen  . Der Totient der Zahl   ist also  .
Es gibt   Zahlen  , deren Totient   ist. Es gibt keine andere natürliche Zahl  , welche kleiner als   ist, für welche die Gleichung   fünf oder mehr Lösungen hat. Somit ist   eine hochtotiente Zahl.
Mit anderen Worten: es gibt genau fünf Zahlen, nämlich  ,  ,  ,   und  , deren Totient   ist. Die Anzahl der Zahlen  , deren Totient   ist, darf jeweils nicht größer oder gleich   sein. Da dies der Fall ist, ist   eine hochtotiente Zahl.
Tatsächlich kommt in der obigen Liste der Totienten der Wert   nur fünf Mal vor, nämlich an der 15., 16., 20., 24. und an der 30. Stelle.
  • Die ersten hochtotienten Zahlen sind die folgenden:
1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640, 11520, 17280, 25920, 30240, 34560, 40320, 51840, 60480, 69120, 80640, 103680, 120960, 161280, 181440, 207360, 241920, 362880, 483840, 725760, 967680, … (Folge A097942 in OEIS)
Die Zahlen dieser Liste werden definitionsbedingt immer größer (im Gegensatz zur Liste, die im nächsten Beispiel steht).
Diese oberen hochtotienten Zahlen sind die Totienten für   Zahlen (aufsteigend für  ):
2, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54, 72, 98, 126, 129, 176, 178, 247, 276, 281, 331, 359, 399, 441, 454, 525, 558, 692, 718, 734, 764, 1023, 1138, 1485, 1755, 2008, 2166, 2590, 2702, 2733, 3169, 3687, 3802, 4133, 4604, 5025, 5841, 6019, 6311, … (Folge A131934 in OEIS)
Beispiel:
An der 7. Stelle der ersten Liste steht die Zahl  . An der 7. Stelle der unteren Liste steht die Zahl  . Das bedeutet, dass es   verschiedene Zahlen gibt, deren Totient   ergibt. Keine andere Zahl kleiner als   ist der Totient von gleich viel oder mehr als   verschiedenen Zahlen, was   zur hochtotienten Zahl macht.
  • Die nächste Liste gibt die kleinsten Zahlen an, welche Totient für   Zahlen sind (aufsteigend für  ):
1, 2, 4, 8, 12, 32, 36, 40, 24, 48, 160, 396, 2268, 704, 312, 72, 336, 216, 936, 144, 624, 1056, 1760, 360, 2560, 384, 288, 1320, 3696, 240, 768, 9000, 432, 7128, 4200, 480, 576, 1296, 1200, 15936, 3312, 3072, 3240, 864, 3120, 7344, 3888, 720, 1680, 4992, … (Folge A007374 in OEIS)
Diese Liste ähnelt sehr der vorigen Liste der hochtotienten Zahlen, es können die Zahlen aber im Gegensatz zur vorigen Liste der hochtotienten Zahlen auch wieder kleiner werden.
Beispiel 1:
An der  -ten Stelle (wenn man mit   zu zählen beginnt) steht die Zahl  . Es gibt somit   Zahlen, deren Totient   ist und es gibt kein  , welche ebenfalls Totient für   Zahlen wäre. Somit ist   der kleinste Wert, für den es   Zahlen gibt, die alle denselben Totient, nämlich  , haben.
Beispiel 2:
An der  -ten Stelle (wenn man mit   zu zählen beginnt) steht die Zahl  . Es gibt somit   Zahlen, deren Totient   ist und es gibt kein  , welche ebenfalls Totient für   Zahlen wäre. Somit ist   der kleinste Wert, für den es   Zahlen gibt, die alle denselben Totient, nämlich  , haben.
Vergleicht man diesen Wert aber mit der Liste der hochtotienten Zahlen direkt darüber, dann stellt man fest, dass dort schon an der  -ten Stelle die Zahl   steht. Diese Zahl ist der Totient von   verschiedenen Zahlen, die alle denselben Totient, nämlich  , haben. Weil es keinen kleineren Wert   gibt, der Totient für   oder mehr Zahlen ist, ist   eine hochtotiente Zahl. Der Wert   ist zwar der kleinste Wert, welcher Totient von   verschiedenen Zahlen ist, da er aber größer als   ist, ist er nicht hochtotient und kommt deswegen in dieser Liste nicht vor.
  • Es folgt eine Tabelle, von der man etwas leichter die hochtotienten Zahlen ablesen kann. In der ersten Spalte sind die aufsteigenden  , in der zweiten Spalte stehen diejenigen Zahlen, deren Totient   ist und in der dritten Spalte kann man die Anzahl der Zahlen ablesen, die in der zweiten Spalte stehen. Jedes Mal, wenn in dieser dritten Spalte eine höhere Zahl steht als in allen anderen Zeilen zuvor, handelt es sich bei   um eine hochtotiente Zahl (welche gelb eingefärbt wird). Am Ende der Tabelle werden noch ein paar ausgewählte weitere   angeführt, die in obigen Beispielen eventuell auftauchen:

Eigenschaften

Bearbeiten
  • Es gibt unendlich viele hochtotiente Zahlen.
  • Die Zahl   ist die einzige ungerade hochtotiente Zahl. Alle anderen hochtotienten Zahlen sind gerade Zahlen.
  • Der Totient   einer Zahl   lässt sich für jedes   aus dessen kanonischer Primfaktorzerlegung   wie folgt berechnen (siehe Allgemeine Berechnungsformel der Eulerschen Phi-Funktion):
 
Somit gilt:
Eine hochtotiente Zahl   ist eine Zahl, die auf mehr Arten in der obigen Form als Produkt dargestellt werden kann als jede andere Zahl  .
Beispiel:
Die hochtotiente Zahl   ist der Totient der fünf Zahlen  ,  ,  ,   und  . Somit gilt:
 

Siehe auch

Bearbeiten
Bearbeiten