Nichtkototient
# Nichtkototient

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

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

    $x-\varphi (x)=n$

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

## Beispiele

* Die Kototienten $n-\varphi (n)$, also die Anzahl der natürlichen Zahlen $x<n$, welche mindestens einen Primfaktor mit $n$ gemeinsam haben, lauten (für $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 $n=10$ ist ein Nichtkototient, weil es keine natürliche Zahl $x$ gibt, für welche exakt $n=10$ Zahlen existieren, die mindestens einen Primfaktor mit $x$ gemeinsam haben und kleiner oder gleich $x$ sind.
* Die Zahl $n=12$ ist kein Nichtkototient:

       Die Zahl $x=18$ ist zu den sechs Zahlen $k\in \{1,5,7,11,13,17\}$ teilerfremd, mit allen anderen 12 Zahlen, welche kleiner oder gleich $x=18$ sind, hat sie einen Primfaktor gemeinsam. Somit ist $18-\varphi (18)=18-6=12$. Der Kototient der Zahl $x=18$ ist somit gleich $12$. Also ist $n=12$ kein Nichtkototient. Weitere $x$ muss man nicht suchen (obwohl auch $x_{2}=20$ und $x_{3}=22$ den Kototienten $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 $k$ an, deren Kototient $n$ ist (für aufsteigende $n=0,1,2,3,\ldots$; falls es keine Zahl mit Kototient $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 $n$-ten Stelle eine $0$ auf (wobei man mit $n=0$ zu zählen beginnen muss), so ist $n$ ein Nichtkototient, weil es offenbar kein $k$ gibt, deren Kototient $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 $k$ an, deren Kototient $n$ ist (für aufsteigende $n=0,1,2,3,\ldots$; falls es keine Zahl mit Kototient $n$ gibt, so wird die Zahl 0 angegeben; der Wert für $n=1$ ist ∞, da alle Primzahlen den Kototienten $n=1$ haben und es somit keine größte Zahl gibt, deren Kototient $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 $n$-ten Stelle eine $0$ auf, so ist $n$ wie in der vorigen Liste ein Nichtkototient (man muss mit $n=0$ zu zählen beginnen).
* Die nächste Liste gibt die Anzahl der $k$ an, deren Kototient $k-\varphi (k)=n$ ist (für aufsteigende $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 $n=0$ mit dem Zählen beginnen) steht die Zahl $k=0$. Das bedeutet, dass es $0$ Zahlen gibt, deren Kototient gleich $n=26$ ist. Somit ist $n=26$ ein Nichtkototient.
* Es folgt eine Tabelle, von der man etwas leichter die Nichtkototienten ablesen kann. In der ersten Spalte sind die aufsteigenden $n$, in der zweiten Spalte stehen diejenigen Zahlen, deren Kototient $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 Kototient haben, handelt es sich bei $n$ um einen Nichtkototienten (welcher gelb eingefärbt wird):

| $n$ | $k$, sodass $k-\varphi (k)=n$ | Anzahl der $k$, sodass $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 |
| $n$ | $k$, sodass $k-\varphi (k)=n$ | Anzahl der $k$, sodass $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 |
| $n$ | $k$, sodass $k-\varphi (k)=n$ | Anzahl der $k$, sodass $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 |
| $n$ | $k$, sodass $k-\varphi (k)=n$ | Anzahl der $k$, sodass $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 und im Jahr 1973 von Paul Erdős aufgeworfen und von Jerzy Browkin und Andrzej Schinzel im Jahr 1995 beantwortet, welche zeigen konnten, dass alle Zahlen der Form $2^{k}\cdot 509203$ mit natürlichen $k\geq 1$ Nichtkototienten sind. Im Jahr 2000 konnten Achim Flammenkamp und Florian Luca noch weitere unendliche Familien hinzufügen, die allesamt Nichtkototienten sind:
          Sei $m\geq 1$ eine natürliche Zahl. Dann sind alle Zahlen der Form $n=2^{m}\cdot k$ mit $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 $n$ ungerade, so wäre nach der goldbachschen Vermutung $n+1=p+q$ für zwei Primzahlen $p$ und $q$. Dann wäre weiter $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.
