Hochtotiente Zahl

Der Totient einer Zahl ${\displaystyle n}$ ist definiert als ${\displaystyle \varphi (n)}$, welche auch Eulersche Phi-Funktion genannt wird und angibt, wie viele zu ${\displaystyle n}$ teilerfremde natürliche Zahlen ${\displaystyle k}$ es gibt, die nicht größer als ${\displaystyle n}$ sind.

In der Zahlentheorie ist eine hochtotiente Zahl (vom englischen highly totient number) eine natürliche Zahl ${\displaystyle n}$, für welche die Gleichung

${\displaystyle \varphi (x)=n}$

mehr Lösungen hat als die Gleichung ${\displaystyle \varphi (x)=k}$ für jede andere natürliche Zahl ${\displaystyle k<n}$.

Eine hochtotiente Zahl, welche Primzahl ist, nennt man hochtotiente Primzahl. Die einzige hochtotiente Primzahl ist ${\displaystyle n=2}$.

• Die Totienten ${\displaystyle \varphi (n)}$, also die Anzahl der zu ${\displaystyle n}$ teilerfremden natürlichen Zahlen ${\displaystyle x<n}$, lauten (für ${\displaystyle n=1,2,3,\ldots }$):

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 ${\displaystyle 4}$. Die Zahl ${\displaystyle n=8}$ hat ${\displaystyle 4}$ teilerfremde Zahlen, welche kleiner als ${\displaystyle n=8}$ sind, nämlich ${\displaystyle 1,3,5}$ und ${\displaystyle 7}$. Daher ist tatsächlich ${\displaystyle \varphi (8)=4}$.

An der 7. Stelle obiger Liste steht die Zahl ${\displaystyle 6}$. Die Zahl ${\displaystyle n=7}$ ist eine Primzahl und hat somit ${\displaystyle 6}$ teilerfremde Zahlen, welche kleiner als ${\displaystyle n=7}$ sind, nämlich alle Zahlen von ${\displaystyle k=1}$ bis ${\displaystyle k=6}$. Somit ist ${\displaystyle \varphi (7)=6}$.

• Eine Primzahl ${\displaystyle p}$ ist nur durch ${\displaystyle 1}$ und sich selbst teilbar. Somit ist sie zu den Zahlen ${\displaystyle 1}$ bis ${\displaystyle p-1}$ teilerfremd. Also ist ${\displaystyle \varphi (p)=p-1}$ (siehe Berechnung der Eulerschen Phi-Funktion). Somit gilt:

${\displaystyle \varphi (p)=p-1}$

Der Totient jeder Primzahl ${\displaystyle p}$ ist somit gleich ${\displaystyle p-1}$.

• Sei ${\displaystyle n:=8}$. Es gibt fünf Lösungen der Gleichung ${\displaystyle \varphi (x)=8}$, nämlich ${\displaystyle x_{1}=15}$, ${\displaystyle x_{2}=16}$, ${\displaystyle x_{3}=20}$, ${\displaystyle x_{4}=24}$ und ${\displaystyle x_{5}=30}$:

Die Zahl ${\displaystyle x_{1}=15}$ ist zu den Zahlen ${\displaystyle 1,2,4,7,8,11,13}$ und ${\displaystyle 14}$ teilerfremd, es gibt also acht zu ${\displaystyle x_{1}=15}$ teilerfremde Zahlen und es ist deswegen ${\displaystyle \varphi (15)=8}$. Der Totient der Zahl ${\displaystyle x_{1}=15}$ ist also ${\displaystyle 8}$.

Die Zahl ${\displaystyle x_{2}=16}$ ist zu den Zahlen ${\displaystyle 1,3,5,7,9,11,13}$ und ${\displaystyle 15}$ teilerfremd, es gibt also acht zu ${\displaystyle x_{2}=16}$ teilerfremde Zahlen und es ist deswegen ${\displaystyle \varphi (16)=8}$. Der Totient der Zahl ${\displaystyle x_{2}=16}$ ist also ${\displaystyle 8}$.

Die Zahl ${\displaystyle x_{3}=20}$ ist zu den Zahlen ${\displaystyle 1,3,7,9,11,13,17}$ und ${\displaystyle 19}$ teilerfremd, es gibt also acht zu ${\displaystyle x_{3}=20}$ teilerfremde Zahlen und es ist deswegen ${\displaystyle \varphi (20)=8}$. Der Totient der Zahl ${\displaystyle x_{3}=20}$ ist also ${\displaystyle 8}$.

Die Zahl ${\displaystyle x_{4}=24}$ ist zu den Zahlen ${\displaystyle 1,5,7,11,13,17,19}$ und ${\displaystyle 23}$ teilerfremd, es gibt also acht zu ${\displaystyle x_{4}=24}$ teilerfremde Zahlen und es ist deswegen ${\displaystyle \varphi (24)=8}$. Der Totient der Zahl ${\displaystyle x_{4}=24}$ ist also ${\displaystyle 8}$.

Die Zahl ${\displaystyle x_{4}=30}$ ist zu den Zahlen ${\displaystyle 1,7,11,13,17,19,23}$ und ${\displaystyle 29}$ teilerfremd, es gibt also acht zu ${\displaystyle x_{5}=30}$ teilerfremde Zahlen und es ist deswegen ${\displaystyle \varphi (30)=8}$. Der Totient der Zahl ${\displaystyle x_{5}=30}$ ist also ${\displaystyle 8}$.

Es gibt ${\displaystyle 5}$ Zahlen ${\displaystyle x}$, deren Totient ${\displaystyle \varphi (x)=8}$ ist. Es gibt keine andere natürliche Zahl ${\displaystyle k}$, welche kleiner als ${\displaystyle n=8}$ ist, für welche die Gleichung ${\displaystyle \varphi (x)=k}$ fünf oder mehr Lösungen hat. Somit ist ${\displaystyle n=8}$ eine hochtotiente Zahl.

Mit anderen Worten: es gibt genau fünf Zahlen, nämlich ${\displaystyle x_{1}=15}$, ${\displaystyle x_{2}=16}$, ${\displaystyle x_{3}=20}$, ${\displaystyle x_{4}=24}$ und ${\displaystyle x_{5}=30}$, deren Totient ${\displaystyle n=8}$ ist. Die Anzahl der Zahlen ${\displaystyle x}$, deren Totient ${\displaystyle n<8}$ ist, darf jeweils nicht größer oder gleich ${\displaystyle 5}$ sein. Da dies der Fall ist, ist ${\displaystyle n=8}$ eine hochtotiente Zahl.

Tatsächlich kommt in der obigen Liste der Totienten der Wert ${\displaystyle 8}$ 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 ${\displaystyle k}$ Zahlen (aufsteigend für ${\displaystyle k=1,2,3,\ldots }$):

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 ${\displaystyle n=48}$. An der 7. Stelle der unteren Liste steht die Zahl ${\displaystyle k=11}$. Das bedeutet, dass es ${\displaystyle 11}$ verschiedene Zahlen gibt, deren Totient ${\displaystyle n=48}$ ergibt. Keine andere Zahl kleiner als ${\displaystyle 48}$ ist der Totient von gleich viel oder mehr als ${\displaystyle 11}$ verschiedenen Zahlen, was ${\displaystyle n=48}$ zur hochtotienten Zahl macht.

• Die nächste Liste gibt die kleinsten Zahlen an, welche Totient für ${\displaystyle k}$ Zahlen sind (aufsteigend für ${\displaystyle k=2,3,4\ldots }$):

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 ${\displaystyle k=5}$-ten Stelle (wenn man mit ${\displaystyle k=2}$ zu zählen beginnt) steht die Zahl ${\displaystyle n=8}$. Es gibt somit ${\displaystyle 5}$ Zahlen, deren Totient ${\displaystyle n=8}$ ist und es gibt kein ${\displaystyle n<8}$, welche ebenfalls Totient für ${\displaystyle 5}$ Zahlen wäre. Somit ist ${\displaystyle n=8}$ der kleinste Wert, für den es ${\displaystyle 5}$ Zahlen gibt, die alle denselben Totient, nämlich ${\displaystyle n=8}$, haben.

Beispiel 2:

An der ${\displaystyle k=7}$-ten Stelle (wenn man mit ${\displaystyle k=2}$ zu zählen beginnt) steht die Zahl ${\displaystyle n=32}$. Es gibt somit ${\displaystyle 7}$ Zahlen, deren Totient ${\displaystyle n=32}$ ist und es gibt kein ${\displaystyle n<32}$, welche ebenfalls Totient für ${\displaystyle 7}$ Zahlen wäre. Somit ist ${\displaystyle n=32}$ der kleinste Wert, für den es ${\displaystyle 7}$ Zahlen gibt, die alle denselben Totient, nämlich ${\displaystyle n=32}$, haben.

Vergleicht man diesen Wert aber mit der Liste der hochtotienten Zahlen direkt darüber, dann stellt man fest, dass dort schon an der ${\displaystyle k=6}$-ten Stelle die Zahl ${\displaystyle n=24}$ steht. Diese Zahl ist der Totient von ${\displaystyle 10}$ verschiedenen Zahlen, die alle denselben Totient, nämlich ${\displaystyle n=24}$, haben. Weil es keinen kleineren Wert ${\displaystyle n<24}$ gibt, der Totient für ${\displaystyle 10}$ oder mehr Zahlen ist, ist ${\displaystyle n=24}$ eine hochtotiente Zahl. Der Wert ${\displaystyle n=32}$ ist zwar der kleinste Wert, welcher Totient von ${\displaystyle 7}$ verschiedenen Zahlen ist, da er aber größer als ${\displaystyle 24}$ 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 ${\displaystyle n}$, in der zweiten Spalte stehen diejenigen Zahlen, deren Totient ${\displaystyle n}$ 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 ${\displaystyle n}$ um eine hochtotiente Zahl (welche gelb eingefärbt wird). Am Ende der Tabelle werden noch ein paar ausgewählte weitere ${\displaystyle n}$ angeführt, die in obigen Beispielen eventuell auftauchen:

Tabelle der Totienten

${\displaystyle n}$	${\displaystyle k}$, sodass ${\displaystyle \varphi (k)=n}$	Anzahl der ${\displaystyle k}$, sodass ${\displaystyle \varphi (k)=n}$ (Folge A014197 in OEIS)
0000		0
0001	1, 2	2
0002	3, 4, 6	3
0003		0
0004	5, 8, 10, 12	4
0005		0
0006	7, 9, 14, 18	4
0007		0
0008	15, 16, 20, 24, 30	5
0009		0
0010	11, 22	2
0011		0
0012	13, 21, 26, 28, 36, 42	6
0013		0
0014		0
0015		0
0016	17, 32, 34, 40, 48, 60	6
0017		0
0018	19, 27, 38, 54	4
0019		0
0020	25, 33, 44, 50, 66	5
0021		0
0022	23, 46	2
0023		0
0024	35, 39, 45, 52, 56, 70, 72, 78, 84, 90	10
0025		0
0026		0
0027		0
0028	29, 58	2
0029		0
0030	31, 62	2
0031		0
0032	51, 64, 68, 80, 96, 102, 120 (erstmaliges Auftreten von 7 Werten)	7
0033		0
0034		0
0035		0
0036	37, 57, 63, 74, 76, 108, 114, 126 (erstmaliges Auftreten von 8 Werten)	8
0037		0
0038		0
0039		0
0040	41, 55, 75, 82, 88, 100, 110, 132, 150 (erstmaliges Auftreten von 9 Werten)	9
0041		0
0042	43, 49, 86, 98	4
0043		0
0044	69, 92, 138	3
0045		0
0046	47, 94	2
0047		0
0048	65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210	11
0049		0
0050		0
…	…	…
0072	73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270	17
0160	187, 205, 328, 352, 374, 400, 410, 440, 492, 528, 600, 660 (erstmaliges Auftreten von 12 Werten)	12
0312	313, 371, 395, 471, 477, 507, 626, 628, 632, 676, 742, 790, 942, 948, 954, 1014 (erstmaliges Auftreten von 16 Werten)	16
0396	397, 437, 469, 597, 603, 621, 794, 796, 874, 938, 1194, 1206, 1242 (erstmaliges Auftreten von 13 Werten)	13
0704	1059, 1173, 1335, 1412, 1424, 1472, 1564, 1780, 1840, 2118, 2136, 2208, 2346, 2670, 2760 (erstmaliges Auftreten von 15 Werten)	15
2268	2269, 2413, 2653, 3411, 3429, 3483, 3969, 4538, 4826, 5306, 6822, 6858, 6966, 7938 (erstmaliges Auftreten von 14 Werten)	14

• Es gibt unendlich viele hochtotiente Zahlen.
• Die Zahl ${\displaystyle n=1}$ ist die einzige ungerade hochtotiente Zahl. Alle anderen hochtotienten Zahlen sind gerade Zahlen.
• Der Totient ${\displaystyle \varphi (x)}$ einer Zahl ${\displaystyle x}$ lässt sich für jedes ${\displaystyle x\in \mathbb {N} ^{+}}$ aus dessen kanonischer Primfaktorzerlegung ${\displaystyle x=\prod _{p\mid x}p^{k_{p}}}$ wie folgt berechnen (siehe Allgemeine Berechnungsformel der Eulerschen Phi-Funktion):

${\displaystyle \varphi (x)=\prod _{p\mid x}p^{k_{p}-1}(p-1)}$

Somit gilt:

Eine hochtotiente Zahl ${\displaystyle n}$ ist eine Zahl, die auf mehr Arten in der obigen Form als Produkt dargestellt werden kann als jede andere Zahl ${\displaystyle k<n}$.

Beispiel:

Die hochtotiente Zahl ${\displaystyle n=8}$ ist der Totient der fünf Zahlen ${\displaystyle x_{1}=15}$, ${\displaystyle x_{2}=16}$, ${\displaystyle x_{3}=20}$, ${\displaystyle x_{4}=24}$ und ${\displaystyle x_{5}=30}$. Somit gilt:

${\displaystyle {\begin{array}{rclclclcl}\varphi (15)&=&\varphi (3\cdot 5)&=&3^{1-1}\cdot (3-1)\cdot 5^{1-1}\cdot (5-1)&=&1\cdot 2\cdot 1\cdot 4&=&8\\\varphi (16)&=&\varphi (2^{4})&=&2^{4-1}\cdot (2-1)&=&8\cdot 1&=&8\\\varphi (20)&=&\varphi (2^{2}\cdot 5)&=&2^{2-1}\cdot (2-1)\cdot 5^{1-1}\cdot (5-1)&=&2\cdot 1\cdot 1\cdot 4&=&8\\\varphi (24)&=&\varphi (2^{3}\cdot 3)&=&2^{3-1}\cdot (2-1)\cdot 3^{1-1}\cdot (3-1)&=&4\cdot 1\cdot 1\cdot 2&=&8\\\varphi (30)&=&\varphi (2\cdot 3\cdot 5)&=&2^{1-1}\cdot (2-1)\cdot 3^{1-1}\cdot (3-1)\cdot 5^{1-1}\cdot (5-1)&=&1\cdot 1\cdot 1\cdot 2\cdot 1\cdot 4&=&8\end{array}}}$

• Eulersche Phi-Funktion
• Hochkototiente Zahl
• Hochzusammengesetzte Zahl
• Nichtkototient
• Nichttotient
• Perfekt totiente Zahl
• Spärlich totiente Zahl

• Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
• Eric W. Weisstein: Nontotient. In: MathWorld (englisch).
• Arndt Brünner: Teilermengen und Primfaktorzerlegungen, Eulers Phi-Funktion und Fakultäten. Berechnung der Eulerschen Phi-Funktion. Abgerufen am 15. Februar 2020 (deutsch).