Der Kototient einer Zahl ist definiert als . Dabei ist die eulersche Phi-Funktion (auch Totient von genannt), welche angibt, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind. Der Wert gibt somit die Anzahl der natürlichen Zahlen an, welche mindestens einen Primfaktor mit gemeinsam haben.
In der Zahlentheorie ist ein Nichtkototient (vom englischen Noncototient) eine natürliche Zahl , welche kein Kototient ist, wenn also die Gleichung
keine Lösung für hat. Mit anderen Worten: ist ein Nichtkototient, wenn keine natürliche Zahl existiert, zu welcher es exakt Zahlen gibt, die mindestens einen Primfaktor mit gemeinsam haben und kleiner oder gleich sind.
Beispiele Die Kototienten , also die Anzahl der natürlichen Zahlen , welche mindestens einen Primfaktor mit gemeinsam haben, lauten (für ): 0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27, … () Die Zahl ist ein Nichtkototient, weil es keine natürliche Zahl gibt, für welche exakt Zahlen existieren, die mindestens einen Primfaktor mit gemeinsam haben und kleiner oder gleich sind. Die Zahl ist kein Nichtkototient: Die Zahl ist zu den sechs Zahlen teilerfremd, mit allen anderen 12 Zahlen, welche kleiner oder gleich sind, hat sie einen Primfaktor gemeinsam. Somit ist . Der Kototient der Zahl ist somit gleich . Also ist kein Nichtkototient. Weitere muss man nicht suchen (obwohl auch und den Kototienten hätten). Die folgenden Zahlen sind die kleinsten Nichtkototienten: 10, 26, 34, 50, 52, 58, 86, 100, 116, 122, 130, 134, 146, 154, 170, 172, 186, 202, 206, 218, 222, 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, 518, 520, … () Die nächste Liste gibt die kleinsten an, deren Kototient ist (für aufsteigende ; falls es keine Zahl mit Kototient gibt, so wird die Zahl 0 angegeben): 1, 2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0, 235, 0, 329, 78, 159, 98, 105, 0, 371, 84, 177, 122, 135, 96, 305, 90, 427, … () Taucht in obiger Liste an der -ten Stelle eine auf (wobei man mit zu zählen beginnen muss), so ist ein Nichtkototient, weil es offenbar kein gibt, deren Kototient ist (wie zum Beispiel an der 10., 26., 34., 50., 52. und 58. Stelle, welche allesamt Nichtkototienten sind). Die nächste Liste gibt die größten an, deren Kototient ist (für aufsteigende ; falls es keine Zahl mit Kototient gibt, so wird die Zahl 0 angegeben; der Wert für ist ∞, da alle Primzahlen den Kototienten haben und es somit keine größte Zahl gibt, deren Kototient ist): 1, ∞, 4, 9, 8, 25, 10, 49, 16, 27, 0, 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0, 187, 52, 841, 58, 961, 64, 253, 0, 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0, 667, 0, 2809, 106, 703, 104, 697, 0, 3481, 118, 3721, 122, … () Taucht in obiger Liste an der -ten Stelle eine auf, so ist wie in der vorigen Liste ein Nichtkototient (man muss mit zu zählen beginnen). Die nächste Liste gibt die Anzahl der an, deren Kototient ist (für aufsteigende ): 1, ∞, 1, 1, 2, 1, 1, 2, 3, 2, 0, 2, 3, 2, 1, 2, 3, 3, 1, 3, 1, 3, 1, 4, 4, 3, 0, 4, 1, 4, 3, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, 5, 1, 7, 1, 8, 1, 5, 2, 6, 1, 9, 2, 6, 0, 4, 2, 10, 2, 4, 2, 5, 2, 7, 5, 4, 1, 8, 0, 9, 1, 6, 1, 7, … () Beispiel: An der 26. Stelle obiger Liste (man muss mit mit dem Zählen beginnen) steht die Zahl . Das bedeutet, dass es Zahlen gibt, deren Kototient gleich ist. Somit ist ein Nichtkototient. Es folgt eine Tabelle, von der man etwas leichter die Nichtkototienten ablesen kann. In der ersten Spalte sind die aufsteigenden , in der zweiten Spalte stehen diejenigen Zahlen, deren Kototient 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 Kototient haben, handelt es sich bei um einen Nichtkototienten (welcher gelb eingefärbt wird):
, sodass Anzahl der , sodass () 0 1 1 1 2, 3, 5, 7, 11, … (alle Primzahlen) ∞ 2 4 1 3 9 1 4 6, 8 2 5 25 1 6 10 1 7 15, 49 2 8 12, 14, 16 3 9 21, 27 210 0 11 35, 121 2 12 18, 20, 22 3 13 33, 169 2 14 26 1 15 39, 55 2 16 24, 28, 32 3 17 65, 77, 289 3 18 34 1 19 51, 91, 361 3 20 38 1 21 45, 57, 85 3 22 30 1 23 95, 119, 143, 529 4 24 36, 40, 44, 46 4 25 69, 125, 133 326 0 27 63, 81, 115, 187 4 28 52 1 29 161, 209, 221, 841 4 30 42, 50, 58 3 31 87, 247, 961 3 32 48, 56, 62, 64 4 33 93, 145, 253 334 0 35 75, 155, 203, 299, 323 5 36 54, 68 2 , sodass Anzahl der , sodass () 37 217, 1369 2 38 74 1 39 99, 111, 319, 391 4 40 76 1 41 185, 341, 377, 437, 1681 5 42 82 1 43 123, 259, 403, 1849 4 44 60, 86 2 45 117, 129, 205, 493 4 46 66, 70 2 47 215, 287, 407, 527, 551, 2209 6 48 72, 80, 88, 92, 94 5 49 141, 301, 343, 481, 589 550 0 51 235, 451, 667 352 0 53 329, 473, 533, 629, 713, 2809 6 54 78, 106 2 55 159, 175, 559, 703 4 56 98, 104 2 57 105, 153, 265, 517, 697 558 0 59 371, 611, 731, 779, 851, 899, 3481 7 60 84, 100, 116, 118 4 61 177, 817, 3721 3 62 122 1 63 135, 147, 171, 183, 295, 583, 799, 943 8 64 96, 112, 124, 128 4 65 305, 413, 689, 893, 989, 1073 6 66 90 1 67 427, 1147, 4489 3 68 134 1 69 201, 649, 901, 1081, 1189 5 70 102, 110 2 71 335, 671, 767, 1007, 1247, 1271, 5041 7 72 108, 136, 142 3 , sodass Anzahl der , sodass () 73 213, 469, 793, 1333, 5329 5 74 146 1 75 207, 219, 275, 355, 1003, 1219, 1363 7 76 148 1 77 245, 365, 497, 737, 1037, 1121, 1457, 1517 8 78 114 1 79 511, 871, 1159, 1591, 6241 5 80 152, 158 2 81 189, 237, 243, 781, 1357, 1537 6 82 130 1 83 395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889 9 84 164, 166 2 85 165, 249, 325, 553, 949, 1273 686 0 87 415, 1207, 1711, 1927 4 88 120, 172 2 89 581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921 10 90 126, 178 2 91 267, 1027, 1387, 1891 4 92 132, 140 2 93 261, 445, 913, 1633, 2173 5 94 138, 154 2 95 623, 1079, 1343, 1679, 1943, 2183, 2279 7 96 144, 160, 176, 184, 188 5 97 1501, 2077, 2257, 9409 4 98 194 1 99 195, 279, 291, 979, 1411, 2059, 2419, 2491 8100 0 101 485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201 9 102 202 1 103 303, 679, 2263, 2479, 2623, 10609 6 104 206 1 105 225, 309, 425, 505, 1513, 1909, 2773 7 106 170 1 107 515, 707, 1067, 1691, 2291, 2627, 2747, 2867, 11449 9 108 156, 162, 212, 214 4 , sodass Anzahl der , sodass () 109 321, 721, 1261, 2449, 2701, 2881, 11881 7 110 150, 182, 218 3 111 231, 327, 535, 1111, 2047, 2407, 2911, 3127 8 112 196, 208 2 113 545, 749, 1133, 1313, 1649, 2573, 2993, 3053, 3149, 3233, 12769 11 114 226 1 115 339, 475, 763, 1339, 1843, 2923, 3139 7116 0 117 297, 333, 565, 1177, 1717, 2581, 3337 7 118 174, 190 2 119 539, 791, 1199, 1391, 1751, 1919, 2231, 2759, 3071, 3239, 3431, 3551, 3599 13 120 168, 200, 232, 236 4 121 1331, 1417, 1957, 3397 4122 0 123 1243, 1819, 2323, 3403, 3763 5 124 244 1 125 625, 1469, 1853, 2033, 2369, 2813, 3293, 3569, 3713, 3869, 3953 11 126 186 1 127 255, 2071, 3007, 4087, 16129 5 128 192, 224, 248, 254, 256 5 129 273, 369, 381, 1921, 2461, 2929, 3649, 3901, 4189 9130 0 131 635, 2147, 2507, 2987, 3131, 3827, 4187, 4307, 4331, 17161 10 132 180, 242, 262 3 133 393, 637, 889, 3193, 3589, 4453 6134 0 135 351, 387, 575, 655, 2599, 3103, 4183, 4399 8 136 268 1 137 917, 1397, 3161, 3317, 3737, 3977, 4661, 4757, 18769 9 138 198, 274 2 139 411, 1651, 3379, 3811, 4171, 4819, 4891, 19321 8 140 204, 220, 278 3 141 285, 417, 685, 1441, 3277, 4141, 4717, 4897 8 142 230, 238 2 143 363, 695, 959, 1703, 2159, 3503, 3959, 4223, 4343, 4559, 5063, 5183 12 144 216, 272, 284 3
Eigenschaften Es gibt unendlich viele Nichtkototienten. Die Frage auf diese Antwort wurde im Jahr 1959 von Wacław SierpińskiWacław Sierpiński: Number Theory, Part II, Warszawa, 1959 (polnisch) und im Jahr 1973 von Paul ErdősPaul Erdős: Über die Zahlen der Form und , Elem. Math. (1973), 83–86 aufgeworfen und von Jerzy Browkin und Andrzej Schinzel im Jahr 1995 beantwortet, welche zeigen konnten, dass alle Zahlen der Form mit natürlichen Nichtkototienten sind. Im Jahr 2000 konnten Achim Flammenkamp und Florian Luca noch weitere unendliche Familien hinzufügen, die allesamt Nichtkototienten sind: Sei eine natürliche Zahl. Dann sind alle Zahlen der Form mit Nichtkototienten (die Zahlen in der Mengenklammer sind allesamt Riesel-Zahlen).
Vermutungen Es wird vermutet, dass alle Nichtkototienten gerade Zahlen sind. Das würde nämlich wie folgt aus der starken goldbachschen Vermutung folgen: Ist ungerade, so wäre nach der goldbachschen Vermutung für zwei Primzahlen und . Dann wäre weiter ein Kototient. Die goldbachsche Vermutung hat also zur Konsequenz, dass alle ungeraden Zahlen Kototienten wären, das heißt umgekehrt müssten alle Nichtkototienten gerade sein.
Siehe auch Eulersche Phi-Funktion Hochkototiente Zahl Hochtotiente Zahl Hochzusammengesetzte Zahl Nichttotient Perfekt totiente Zahl Spärlich totiente Zahl
Weblinks
Einzelnachweise
Kategorie:Ganzzahlmenge Kategorie:Zahlentheorie