In der Zahlentheorie ist der Totient einer natürlichen Zahl definiert als die Anzahl der zu teilerfremden natürlichen Zahlen, die nicht größer als sind. wird auch eulersche Phi-Funktion genannt. Ein Nichttotient (vom englischen Nontotient) ist eine natürliche Zahl , die kein Totient ist, also eine Zahl, für die Gleichung
keine Lösung für hat. Mit anderen Worten: Eine natürliche Zahl ist ein Nichttotient, wenn es keine natürliche Zahl gibt, zu der es exakt teilerfremde Zahlen gibt.
Beispiele Die Zahl ist ein Nichttotient, weil es keine natürliche Zahl gibt, für welche exakt teilerfremde Zahlen existieren, die kleiner als sind. Die Zahl ist kein Nichttotient: Die Primzahl ist zu Zahlen teilerfremd, somit ist auch . Die Gleichung hat also mindestens eine Lösung , also ist kein Nichttotient. Weitere muss man nicht suchen (obwohl auch die Zahlen , und den Totienten hätten). Die Zahl ist kein Nichttotient: Die Zahl ist als Sonderfall des leeren Produkts (weder Primzahl noch zusammengesetzte Zahl) auch zu sich selbst teilerfremd, also ist . Außerdem ist die Zahl zu teilerfremd, somit ist auch . Somit hat die Gleichung sogar zwei Lösungen und , also ist 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, … () Die nächste Liste gibt die kleinsten an, deren Totient ist (für aufsteigende ) 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, … () Taucht in obiger Liste an der -ten Stelle eine auf, so ist ein Nichttotient, weil es offenbar kein gibt, deren Totient ist. Die nächste Liste gibt die größten an, deren Totient ist (für aufsteigende ) 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, … () Taucht in obiger Liste an der -ten Stelle eine auf, so ist ein Nichttotient, weil es offenbar kein gibt, deren Totient ist. Die folgende Liste gibt die Anzahl der verschiedenen an, für welche gilt (für aufsteigende ): 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, … () Beispiel: An der -ten Stelle steht die Zahl . Das bedeutet, dass es Lösungen der Gleichung gibt. Somit ist 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 für jedes 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 , 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 Null steht, wenn es also keine Zahlen gibt, welche als Totient haben, handelt es sich bei um einen Nichttotienten (welcher gelb eingefärbt wird):
, sodass Anzahl der , sodass () 1 1, 2 2 2 3, 4, 6 33 0 4 5, 8, 10, 12 45 0 6 7, 9, 14, 18 47 0 8 15, 16, 20, 24, 30 59 0 10 11, 22 211 0 12 13, 21, 26, 28, 36, 42 613 014 015 0 16 17, 32, 34, 40, 48, 60 617 0 18 19, 27, 38, 54 419 0 20 25, 33, 44, 50, 66 521 0 22 23, 46 223 0 24 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 1025 026 027 0 28 29, 58 229 0 30 31, 62 231 0 32 51, 64, 68, 80, 96, 102, 120 733 034 035 0 36 37, 57, 63, 74, 76, 108, 114, 126 8 , sodass Anzahl der , sodass ()37 038 039 0 40 41, 55, 75, 82, 88, 100, 110, 132, 150 941 0 42 43, 49, 86, 98 443 0 44 69, 92, 138 345 0 46 47, 94 247 0 48 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 1149 050 051 0 52 53, 106 253 0 54 81, 162 255 0 56 87, 116, 174 357 0 58 59, 118 259 0 60 61, 77, 93, 99, 122, 124, 154, 186, 198 961 062 063 0 64 85, 128, 136, 160, 170, 192, 204, 240 865 0 66 67, 134 267 068 069 0 70 71, 142 271 0 72 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 17 , sodass Anzahl der , sodass ()73 074 075 076 077 0 78 79, 158 279 0 80 123, 164, 165, 176, 200, 220, 246, 264, 300, 330 1081 0 82 83, 166 283 0 84 129, 147, 172, 196, 258, 294 685 086 087 0 88 89, 115, 178, 184, 230, 276 689 090 091 0 92 141, 188, 282 393 094 095 0 96 97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420 1797 098 099 0 100 101, 125, 202, 250 4101 0 102 103, 206 2103 0 104 159, 212, 318 3105 0 106 107, 214 2107 0 108 109, 133, 171, 189, 218, 266, 324, 342, 378 9 , sodass Anzahl der , sodass ()109 0 110 121, 242 2111 0 112 113, 145, 226, 232, 290, 348 6113 0114 0115 0 116 177, 236, 354 3117 0118 0119 0 120 143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396, 450, 462 17121 0122 0123 0124 0125 0 126 127, 254 2127 0 128 255, 256, 272, 320, 340, 384, 408, 480, 510 9129 0 130 131, 262 2131 0 132 161, 201, 207, 268, 322, 402, 414 7133 0134 0135 0 136 137, 274 2137 0 138 139, 278 2139 0 140 213, 284, 426 3141 0142 0143 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 eine Primzahl. Dann ist niemals ein Nichttotient. Beweis: Jede Primzahl ist zu Zahlen teilerfremd (nämlich zu allen natürlichen Zahlen, welche kleiner als sind). Somit ist und ist der Totient von . Also ist kein Nichttotient. Sei eine Primzahl. Dann ist die Rechteckzahl niemals ein Nichttotient. Beweis: Wegen den Rechenregeln für die eulersche Phi-Funktion für Primzahlpotenzen erhält man . Somit ist und ist der Totient von . Also ist kein Nichttotient. Alle ungeraden Zahlen außer der Zahl sind Nichttotienten. Für jede natürliche Zahl existiert eine Primzahl , sodass ein Nichttotient ist. Es gibt unendlich viele Primzahlen , sodass alle Zahlen der Form mit Nichttotienten sind (wie zum Beispiel die Sierpinski-Zahlen und ). 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
Einzelnachweise
Kategorie:Ganzzahlmenge Kategorie:Zahlentheorie