Nichtkototient

Der Kototient einer Zahl ${\displaystyle n}$ ist definiert als ${\displaystyle n-\varphi (n)}$. Dabei ist ${\displaystyle \varphi (n)}$ die eulersche Phi-Funktion (auch Totient von ${\displaystyle n}$ genannt), welche angibt, wie viele zu ${\displaystyle n}$ teilerfremde natürliche Zahlen es gibt, die nicht größer als ${\displaystyle n}$ sind. Der Wert ${\displaystyle n-\varphi (n)}$ gibt somit die Anzahl der natürlichen Zahlen ${\displaystyle 0<x\leq n}$ an, welche mindestens einen Primfaktor mit ${\displaystyle n}$ gemeinsam haben.

In der Zahlentheorie ist ein Nichtkototient (vom englischen Noncototient) eine natürliche Zahl ${\displaystyle n}$, welche kein Kototient ist, wenn also die Gleichung

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

keine Lösung für ${\displaystyle x}$ hat. Mit anderen Worten: ${\displaystyle n}$ ist ein Nichtkototient, wenn keine natürliche Zahl ${\displaystyle x}$ existiert, zu welcher es exakt ${\displaystyle n}$ Zahlen gibt, die mindestens einen Primfaktor mit ${\displaystyle x}$ gemeinsam haben und kleiner oder gleich ${\displaystyle x}$ sind.

Beispiele

• Die Kototienten ${\displaystyle n-\varphi (n)}$, also die Anzahl der natürlichen Zahlen ${\displaystyle x<n}$, welche mindestens einen Primfaktor mit ${\displaystyle n}$ gemeinsam haben, lauten (für ${\displaystyle n=1,2,3,\ldots }$):

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, … (Folge A051953 in OEIS)

• Die Zahl ${\displaystyle n=10}$ ist ein Nichtkototient, weil es keine natürliche Zahl ${\displaystyle x}$ gibt, für welche exakt ${\displaystyle n=10}$ Zahlen existieren, die mindestens einen Primfaktor mit ${\displaystyle x}$ gemeinsam haben und kleiner oder gleich ${\displaystyle x}$ sind.
• Die Zahl ${\displaystyle n=12}$ ist kein Nichtkototient:

Die Zahl ${\displaystyle x=18}$ ist zu den sechs Zahlen ${\displaystyle k\in \{1,5,7,11,13,17\}}$ teilerfremd, mit allen anderen 12 Zahlen, welche kleiner oder gleich ${\displaystyle x=18}$ sind, hat sie einen Primfaktor gemeinsam. Somit ist ${\displaystyle 18-\varphi (18)=18-6=12}$. Der Kototient der Zahl ${\displaystyle x=18}$ ist somit gleich ${\displaystyle 12}$. Also ist ${\displaystyle n=12}$ kein Nichtkototient. Weitere ${\displaystyle x}$ muss man nicht suchen (obwohl auch ${\displaystyle x_{2}=20}$ und ${\displaystyle x_{3}=22}$ den Kototienten ${\displaystyle n=12}$ 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, … (Folge A005278 in OEIS)

• Die nächste Liste gibt die kleinsten ${\displaystyle k}$ an, deren Kototient ${\displaystyle n}$ ist (für aufsteigende ${\displaystyle n=0,1,2,3,\ldots }$; falls es keine Zahl mit Kototient ${\displaystyle n}$ 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, … (Folge A063507 in OEIS)

Taucht in obiger Liste an der ${\displaystyle n}$-ten Stelle eine ${\displaystyle 0}$ auf (wobei man mit ${\displaystyle n=0}$ zu zählen beginnen muss), so ist ${\displaystyle n}$ ein Nichtkototient, weil es offenbar kein ${\displaystyle k}$ gibt, deren Kototient ${\displaystyle n}$ 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 ${\displaystyle k}$ an, deren Kototient ${\displaystyle n}$ ist (für aufsteigende ${\displaystyle n=0,1,2,3,\ldots }$; falls es keine Zahl mit Kototient ${\displaystyle n}$ gibt, so wird die Zahl 0 angegeben; der Wert für ${\displaystyle n=1}$ ist ∞, da alle Primzahlen den Kototienten ${\displaystyle n=1}$ haben und es somit keine größte Zahl gibt, deren Kototient ${\displaystyle n=1}$ 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, … (Folge A063748 in OEIS)

Taucht in obiger Liste an der ${\displaystyle n}$-ten Stelle eine ${\displaystyle 0}$ auf, so ist ${\displaystyle n}$ wie in der vorigen Liste ein Nichtkototient (man muss mit ${\displaystyle n=0}$ zu zählen beginnen).

• Die nächste Liste gibt die Anzahl der ${\displaystyle k}$ an, deren Kototient ${\displaystyle k-\varphi (k)=n}$ ist (für aufsteigende ${\displaystyle n=0,1,2,3,\ldots }$):

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, … (Folge A063740 in OEIS)

Beispiel:

An der 26. Stelle obiger Liste (man muss mit ${\displaystyle n=0}$ mit dem Zählen beginnen) steht die Zahl ${\displaystyle k=0}$. Das bedeutet, dass es ${\displaystyle 0}$ Zahlen gibt, deren Kototient gleich ${\displaystyle n=26}$ ist. Somit ist ${\displaystyle n=26}$ ein Nichtkototient.

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

Tabelle der Kototienten

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ Anzahl der ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ (Folge A063740 in OEIS) 00 1 1 01 2, 3, 5, 7, 11, … (alle Primzahlen) ∞ 02 4 1 03 9 1 04 6, 8 2 05 25 1 06 10 1 07 15, 49 2 08 12, 14, 16 3 09 21, 27 2 10 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 3 26 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 3 34 0 35 75, 155, 203, 299, 323 5 36 54, 68 2

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ Anzahl der ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ (Folge A063740 in OEIS) 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 5 50 0 51 235, 451, 667 3 52 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 5 58 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

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ Anzahl der ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ (Folge A063740 in OEIS) 073 213, 469, 793, 1333, 5329 5 074 146 1 075 207, 219, 275, 355, 1003, 1219, 1363 7 076 148 1 077 245, 365, 497, 737, 1037, 1121, 1457, 1517 8 078 114 1 079 511, 871, 1159, 1591, 6241 5 080 152, 158 2 081 189, 237, 243, 781, 1357, 1537 6 082 130 1 083 395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889 9 084 164, 166 2 085 165, 249, 325, 553, 949, 1273 6 086 0 087 415, 1207, 1711, 1927 4 088 120, 172 2 089 581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921 10 090 126, 178 2 091 267, 1027, 1387, 1891 4 092 132, 140 2 093 261, 445, 913, 1633, 2173 5 094 138, 154 2 095 623, 1079, 1343, 1679, 1943, 2183, 2279 7 096 144, 160, 176, 184, 188 5 097 1501, 2077, 2257, 9409 4 098 194 1 099 195, 279, 291, 979, 1411, 2059, 2419, 2491 8 100 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

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ Anzahl der ${\displaystyle k}$, sodass ${\displaystyle k-\varphi (k)=n}$ (Folge A063740 in OEIS) 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 7 116 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 4 122 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 9 130 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 6 134 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ński[1] und im Jahr 1973 von Paul Erdős[2] aufgeworfen[3] und von Jerzy Browkin und Andrzej Schinzel im Jahr 1995 beantwortet, welche zeigen konnten, dass alle Zahlen der Form ${\displaystyle 2^{k}\cdot 509203}$ mit natürlichen ${\displaystyle k\geq 1}$ Nichtkototienten sind.[4] Im Jahr 2000 konnten Achim Flammenkamp und Florian Luca noch weitere unendliche Familien hinzufügen, die allesamt Nichtkototienten sind:[5]

Sei ${\displaystyle m\geq 1}$ eine natürliche Zahl. Dann sind alle Zahlen der Form ${\displaystyle n=2^{m}\cdot k}$ mit ${\displaystyle k\in \{509203,2554843,9203917,9545351,10645867,11942443,65484763\}}$ 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 ${\displaystyle n}$ ungerade, so wäre nach der goldbachschen Vermutung ${\displaystyle n+1=p+q}$ für zwei Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$. Dann wäre weiter ${\displaystyle pq-\varphi (pq)=pq-(p-1)(q-1)=p+q-1=n}$ 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

• Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
• Eric W. Weisstein: Noncototient. In: MathWorld (englisch).
• Arndt Brünner: Teilermengen und Primfaktorzerlegungen, Eulers Phi-Funktion und Fakultäten. Berechnung der Eulerschen Phi-Funktion. Abgerufen am 29. Februar 2020.
• Aleksander Grytczuk, Barbara Mędryk: On a result of Flammenkamp-Luca concerning Noncototient sequence. Tsukuba .J. Math. 29 (2), 2005, S. 533–538, abgerufen am 29. Februar 2020.

Einzelnachweise

1. Wacław Sierpiński: Number Theory, Part II, Warszawa, 1959 (polnisch)
2. Paul Erdős: Über die Zahlen der Form ${\displaystyle \sigma (n)-n}$ und ${\displaystyle n-\varphi (n)}$, Elem. Math. (1973), 83–86
3. Achim Flammenkamp, Florian Luca: Infinite families of noncototients. Einleitung. Colloquium Mathematicum 86 (1), 2000, S. 37–41, abgerufen am 29. Februar 2020.
4. Jerzy Browkin, Andrzej Schinzel: On integers not of the form n-φ(n). Theorem. Colloquium Mathematicum 68 (1), 1995, S. 55–58, abgerufen am 29. Februar 2020.
5. Achim Flammenkamp, Florian Luca: Infinite families of noncototients. Theorem. Colloquium Mathematicum 86 (1), 2000, S. 37–41, abgerufen am 29. Februar 2020.