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):

Tabelle der Kototienten

$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^[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

2^{k}\cdot 509203

mit natürlichen

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

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.

Siehe auch

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

↑ Wacław Sierpiński: Number Theory, Part II, Warszawa, 1959 (polnisch)
↑ Paul Erdős: Über die Zahlen der Form $\sigma (n)-n$ und $n-\varphi (n)$ , Elem. Math. (1973), 83–86
↑ Achim Flammenkamp, Florian Luca: Infinite families of noncototients. Einleitung. Colloquium Mathematicum 86 (1), 2000, S. 37–41, abgerufen am 29. Februar 2020.
↑ 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.
↑ Achim Flammenkamp, Florian Luca: Infinite families of noncototients. Theorem. Colloquium Mathematicum 86 (1), 2000, S. 37–41, abgerufen am 29. Februar 2020.

[1] Wacław Sierpiński: Number Theory, Part II, Warszawa, 1959 (polnisch)

[2] Paul Erdős: Über die Zahlen der Form $\sigma (n)-n$ und $n-\varphi (n)$ , Elem. Math. (1973), 83–86

[Flammenkamp-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.

[1]

[2]

[3]

[4]

[5]

Fahrer / Team für die Suche eingeben: