# 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. Die Vermutung ist also äquivalent dazu, dass in obiger Liste niemals eine 1 auftaucht (siehe Carmichaels Totientenfunktions-Vermutung).
* 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):
| $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).