Nichttotient

In der Zahlentheorie ist der Totient einer natürlichen Zahl $n$ definiert als die Anzahl $\varphi (n)$ der zu $n$ teilerfremden natürlichen Zahlen, die nicht größer als $n$ sind. $\varphi$ wird auch eulersche Phi-Funktion genannt. Ein Nichttotient (vom englischen Nontotient) ist eine natürliche Zahl $n$, die kein Totient ist, also eine Zahl, für die Gleichung

$\varphi (x)=n$

keine Lösung für $x$ hat. Mit anderen Worten: Eine natürliche Zahl $n$ ist ein Nichttotient, wenn es keine natürliche Zahl $x$ gibt, zu der es exakt $n$ teilerfremde Zahlen $\leq x$ gibt.

Beispiele

• Die Zahl $n=7$ ist ein Nichttotient, weil es keine natürliche Zahl $x$ gibt, für welche exakt $n=7$ teilerfremde Zahlen existieren, die kleiner als $x$ sind.
• Die Zahl $n=4$ ist kein Nichttotient:

Die Primzahl $p=5$ ist zu $p-1=4$ Zahlen teilerfremd, somit ist auch $\varphi (5)=4$. Die Gleichung $\varphi (x)=n=4$ hat also mindestens eine Lösung $x=5$, also ist $n=4$ kein Nichttotient. Weitere $x$ muss man nicht suchen (obwohl auch die Zahlen $x_{2}=8$, $x_{3}=10$ und $x_{4}=12$ den Totienten $n=4$ hätten).

• Die Zahl $n=1$ ist kein Nichttotient:

Die Zahl $x=1$ ist als Sonderfall des leeren Produkts (weder Primzahl noch zusammengesetzte Zahl) auch zu sich selbst teilerfremd, also ist $\varphi (1)=1$. Außerdem ist die Zahl $x=2$ zu $1$ teilerfremd, somit ist auch $\varphi (2)=1$. Somit hat die Gleichung $\varphi (x)=n=1$ sogar zwei Lösungen $x_{1}=1$ und $x_{2}=2$, also ist $n=1$ kein Nichttotient.

• Die folgenden Zahlen sind die kleinsten geraden Nichttotienten:

14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, 302, 304, 308, 314, 318, … (Folge A005277 in OEIS)

• Die nächste Liste gibt die kleinsten $k$ an, deren Totient $n$ ist (für aufsteigende $n=1,2,3,\ldots$)

1, 3, 0, 5, 0, 7, 0, 15, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 25, 0, 23, 0, 35, 0, 0, 0, 29, 0, 31, 0, 51, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 69, 0, 47, 0, 65, 0, 0, 0, 53, 0, 81, 0, 87, 0, 59, 0, 61, 0, 0, 0, 85, 0, 67, 0, 0, 0, 71, 0, 73, 0, 0, 0, 0, 0, 79, 0, 123, 0, 83, 0, 129, 0, 0, 0, 89, … (Folge A049283 in OEIS)

Taucht in obiger Liste an der $n$-ten Stelle eine $0$ auf, so ist $n$ ein Nichttotient, weil es offenbar kein $k$ gibt, deren Totient $n$ ist.

• Die nächste Liste gibt die größten $k$ an, deren Totient $n$ ist (für aufsteigende $n=1,2,3,\ldots$)

2, 6, 0, 12, 0, 18, 0, 30, 0, 22, 0, 42, 0, 0, 0, 60, 0, 54, 0, 66, 0, 46, 0, 90, 0, 0, 0, 58, 0, 62, 0, 120, 0, 0, 0, 126, 0, 0, 0, 150, 0, 98, 0, 138, 0, 94, 0, 210, 0, 0, 0, 106, 0, 162, 0, 174, 0, 118, 0, 198, 0, 0, 0, 240, 0, 134, 0, 0, 0, 142, 0, 270, 0, 0, 0, 0, 0, 158, 0, 330, 0, … (Folge A057635 in OEIS)

Taucht in obiger Liste an der $n$-ten Stelle eine $0$ auf, so ist $n$ ein Nichttotient, weil es offenbar kein $k$ gibt, deren Totient $n$ ist.

• Die folgende Liste gibt die Anzahl der verschiedenen $k$ an, für welche $\varphi (k)=n$ gilt (für aufsteigende $n=1,2,3,\ldots$):

2, 3, 0, 4, 0, 4, 0, 5, 0, 2, 0, 6, 0, 0, 0, 6, 0, 4, 0, 5, 0, 2, 0, 10, 0, 0, 0, 2, 0, 2, 0, 7, 0, 0, 0, 8, 0, 0, 0, 9, 0, 4, 0, 3, 0, 2, 0, 11, 0, 0, 0, 2, 0, 2, 0, 3, 0, 2, 0, 9, 0, 0, 0, 8, 0, 2, 0, 0, 0, 2, 0, 17, 0, 0, 0, 0, 0, 2, 0, 10, 0, 2, 0, 6, 0, 0, 0, 6, 0, 0, 0, 3, … (Folge A014197 in OEIS)

Beispiel:

An der $n=5$-ten Stelle steht die Zahl $0$. Das bedeutet, dass es $0$ Lösungen der Gleichung $\varphi (k)=n=5$ gibt. Somit ist $n=5$ ein Nichttotient.

Es gibt eine Vermutung von Robert Daniel Carmichael aus dem Jahr 1907, welche besagt, dass es entweder keine oder mindestens zwei Lösungen der Gleichung $\varphi (x)=n$ für jedes $n$ gibt (siehe Carmichaels Vermutung über die Totientfunktion (en)). Die Vermutung ist also äquivalent dazu, dass in obiger Liste niemals eine 1 auftaucht.

• Es folgt eine Tabelle, aus der man etwas leichter die Nichttotienten ablesen kann. In der ersten Spalte sind die aufsteigenden $n$, in der zweiten Spalte stehen diejenigen Zahlen, deren Totient $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 Null steht, wenn es also keine Zahlen gibt, welche $n$ als Totient haben, handelt es sich bei $n$ um einen Nichttotienten (welcher gelb eingefärbt wird):

Tabelle der Totienten

$n$ $k$, sodass $\varphi (k)=n$ Anzahl der $k$, sodass $\varphi (k)=n$ (Folge A014197 in OEIS) 01 1, 2 2 02 3, 4, 6 3 03 0 04 5, 8, 10, 12 4 05 0 06 7, 9, 14, 18 4 07 0 08 15, 16, 20, 24, 30 5 09 0 10 11, 22 2 11 0 12 13, 21, 26, 28, 36, 42 6 13 0 14 0 15 0 16 17, 32, 34, 40, 48, 60 6 17 0 18 19, 27, 38, 54 4 19 0 20 25, 33, 44, 50, 66 5 21 0 22 23, 46 2 23 0 24 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 10 25 0 26 0 27 0 28 29, 58 2 29 0 30 31, 62 2 31 0 32 51, 64, 68, 80, 96, 102, 120 7 33 0 34 0 35 0 36 37, 57, 63, 74, 76, 108, 114, 126 8

$n$ $k$, sodass $\varphi (k)=n$ Anzahl der $k$, sodass $\varphi (k)=n$ (Folge A014197 in OEIS) 37 0 38 0 39 0 40 41, 55, 75, 82, 88, 100, 110, 132, 150 9 41 0 42 43, 49, 86, 98 4 43 0 44 69, 92, 138 3 45 0 46 47, 94 2 47 0 48 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 11 49 0 50 0 51 0 52 53, 106 2 53 0 54 81, 162 2 55 0 56 87, 116, 174 3 57 0 58 59, 118 2 59 0 60 61, 77, 93, 99, 122, 124, 154, 186, 198 9 61 0 62 0 63 0 64 85, 128, 136, 160, 170, 192, 204, 240 8 65 0 66 67, 134 2 67 0 68 0 69 0 70 71, 142 2 71 0 72 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 17

$n$ $k$, sodass $\varphi (k)=n$ Anzahl der $k$, sodass $\varphi (k)=n$ (Folge A014197 in OEIS) 073 0 074 0 075 0 076 0 077 0 078 79, 158 2 079 0 080 123, 164, 165, 176, 200, 220, 246, 264, 300, 330 10 081 0 082 83, 166 2 083 0 084 129, 147, 172, 196, 258, 294 6 085 0 086 0 087 0 088 89, 115, 178, 184, 230, 276 6 089 0 090 0 091 0 092 141, 188, 282 3 093 0 094 0 095 0 096 97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420 17 097 0 098 0 099 0 100 101, 125, 202, 250 4 101 0 102 103, 206 2 103 0 104 159, 212, 318 3 105 0 106 107, 214 2 107 0 108 109, 133, 171, 189, 218, 266, 324, 342, 378 9

$n$ $k$, sodass $\varphi (k)=n$ Anzahl der $k$, sodass $\varphi (k)=n$ (Folge A014197 in OEIS) 109 0 110 121, 242 2 111 0 112 113, 145, 226, 232, 290, 348 6 113 0 114 0 115 0 116 177, 236, 354 3 117 0 118 0 119 0 120 143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396, 450, 462 17 121 0 122 0 123 0 124 0 125 0 126 127, 254 2 127 0 128 255, 256, 272, 320, 340, 384, 408, 480, 510 9 129 0 130 131, 262 2 131 0 132 161, 201, 207, 268, 322, 402, 414 7 133 0 134 0 135 0 136 137, 274 2 137 0 138 139, 278 2 139 0 140 213, 284, 426 3 141 0 142 0 143 0 144 185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630 21

Eigenschaften

• Sei $p\in \mathbb {P}$ eine Primzahl. Dann ist $p-1$ niemals ein Nichttotient.

Beweis:

Jede Primzahl $p$ ist zu $p-1$ Zahlen teilerfremd (nämlich zu allen natürlichen Zahlen, welche kleiner als $p$ sind). Somit ist $\varphi (p)=p-1$ und $p-1$ ist der Totient von $p$. Also ist $p-1$ kein Nichttotient. $\Box$

• Sei $p\in \mathbb {P}$ eine Primzahl. Dann ist die Rechteckzahl $p\cdot (p-1)$ niemals ein Nichttotient.

Beweis:

Wegen den Rechenregeln für die eulersche Phi-Funktion für Primzahlpotenzen erhält man $\varphi (p^{2})=p^{2}\cdot (1-{\frac {1}{p}})=p^{2}-p=p\cdot (p-1)$. Somit ist $\varphi (p^{2})=p\cdot (p-1)$ und $p(p-1)$ ist der Totient von $p^{2}$. Also ist $p\cdot (p-1)$ kein Nichttotient. $\Box$

• Alle ungeraden Zahlen außer der Zahl $n=1$ sind Nichttotienten.
• Für jede natürliche Zahl $m$ existiert eine Primzahl $p$, sodass $mp$ ein Nichttotient ist.
• Es gibt unendlich viele Primzahlen $p$, sodass alle Zahlen der Form $2^{a}\cdot p$ mit $a\in \mathbb {N}$ Nichttotienten sind (wie zum Beispiel die Sierpinski-Zahlen $p=78557$ und $p=271129$).
• Jede ungerade Zahl hat ein gerades Vielfaches, welches Nichttotient ist.
• Es gibt unendlich viele gerade Nichttotienten (folgt aus den vorhergehenden Eigenschaften).

Siehe auch

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

Weblinks

• 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). 
• Mingzhi Zhang: On Nontotients. Journal of Number Theory 43 (2), Februar 1993, S. 168–172, abgerufen am 26. Februar 2020.