Hochkototiente Zahl

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 eine hochkototiente Zahl (vom englischen highly cototient number) eine natürliche Zahl $n>1$, für welche die Gleichung

$x-\varphi (x)=n$

mehr Lösungen hat als die Gleichung $x-\varphi (x)=k$ für jede andere natürliche Zahl $1<k<n$.

Eine hochkototiente Zahl, welche Primzahl ist, nennt man hochkototiente Primzahl.

Beispiele

• Die Kototienten $n-\varphi (n)$, also die Anzahl der positiven ganzen Zahlen $x\leq 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)

Beispiel:

An der 7. Stelle obiger Liste steht die Zahl $1$. Die Zahl $n=7$ hat $6$ teilerfremde Zahlen, welche kleiner als $n=7$ sind (nämlich alle von $1$ bis $6$), somit ist $\varphi (7)=6$ und daher ist tatsächlich $7-\varphi (7)=7-6=1$.

Mit anderen Worten: Die Zahl $n=7$ hat nur mit der Zahl $x=7$ mindestens einen Primfaktor gemeinsam, deswegen ist der Kototient von $n=7$ gleich $1$.

An der 6. Stelle obiger Liste steht die Zahl $4$. Die Zahl $n=6$ hat $2$ teilerfremde Zahlen, welche kleiner als $n=6$ sind, nämlich $k=1$ und $k=5$. Somit ist $\varphi (6)=2$ und daher ist tatsächlich $6-\varphi (6)=6-2=4$.

Mit anderen Worten: Die Zahl $n=6$ hat mit den Zahlen $x_{1}=2$, $x_{2}=3$, $x_{3}=4$ und $x_{4}=6$ mindestens einen Primfaktor gemeinsam, deswegen ist der Kototient von $n=6$ gleich $4$.

• Eine Primzahl $p$ ist nur durch $1$ und sich selbst teilbar. Somit ist sie zu den Zahlen $1$ bis $p-1$ teilerfremd. Also ist $\varphi (p)=p-1$ (siehe Berechnung der Eulerschen Phi-Funktion). Somit gilt:

$p-\varphi (p)=p-(p-1)=p-p 1=1$

Der Kototient jeder Primzahl ist somit gleich $1$ (was klar sein sollte, zumal jede Primzahl nur mit sich selbst mindestens einen Primfaktor gemeinsam hat). Es gibt unendlich viele Primzahlen, also gibt es auch unendlich viele Lösungen der Gleichung $x-\varphi (x)=n$ für $n=1$. Wenn man also für hochkototiente Zahlen die Zahl $n=1$ erlauben würde, gäbe es keine weiteren natürlichen Zahlen $k$, welche für die Gleichung $x-\varphi (x)=k$ mehr Lösungen als $k=n=1$ hätte. Deswegen wird $n=1$ als Sonderfall per Definition ausgeschlossen, es muss deswegen $n>1$ sein.

• Sei $n:=4$. Es gibt zwei Lösungen der Gleichung $x-\varphi (x)=4$, nämlich $x_{1}=6$ und $x_{2}=8$:

Die Zahl $x_{1}=6$ ist zu den Zahlen $1$ und $5$ teilerfremd, es gibt also zwei zu $x_{1}=6$ teilerfremde Zahlen und es ist deswegen $\varphi (6)=2$. Somit ist $6-\varphi (6)=6-2=4$. Der Kototient der Zahl $x_{1}=6$ ist also $4$, es gibt $4$ Zahlen, die kleiner oder gleich $6$ sind, welche mit $x_{1}=6$ mindestens einen Primfaktor gemeinsam haben.

Die Zahl $x_{2}=8$ ist zu den Zahlen $1,3,5$ und $7$ teilerfremd, es gibt also vier zu $x_{2}=8$ teilerfremde Zahlen und es ist deswegen $\varphi (8)=4$. Somit ist $8-\varphi (8)=8-4=4$. Der Kototient der Zahl $x_{2}=8$ ist also ebenfalls $4$, es gibt $4$ Zahlen, die kleiner oder gleich $8$ sind, welche mit $x_{2}=8$ mindestens einen Primfaktor gemeinsam haben.

Es gibt keine andere natürliche Zahl $k>1$, welche kleiner als $n=4$ ist, für welche die Gleichung $x-\varphi (x)=k$ zwei oder mehr Lösungen hat. Somit ist $n=4$ eine hochkototiente Zahl.

Mit anderen Worten: es gibt genau zwei Zahlen, nämlich $x_{1}=6$ und $x_{2}=8$, deren Kototient $n=4$ ist. Die Anzahl der Zahlen, deren Kototient $n<4$ ist, darf jeweils nicht größer oder gleich $2$ sein. Da dies der Fall ist, ist $n=4$ eine hochkototiente Zahl.

Tatsächlich kommt in der obigen Liste der Kototienten der Wert $4$ nur zwei Mal vor, nämlich an der 6. und an der 8. Stelle.

• Sei $n:=8$. Es gibt drei Lösungen der Gleichung $x-\varphi (x)=8$, nämlich $x_{1}=12$, $x_{2}=14$ und $x_{3}=16$:

Die Zahl $x_{1}=12$ ist zu den Zahlen $1,5,7$ und $11$ teilerfremd, es gibt also vier zu $x_{1}=12$ teilerfremde Zahlen und es ist $\varphi (12)=4$. Somit ist $12-\varphi (12)=12-4=8$.

Die Zahl $x_{2}=14$ ist zu den Zahlen $1,3,5,9,11$ und $13$ teilerfremd, es gibt also sechs zu $x_{2}=14$ teilerfremde Zahlen und es ist $\varphi (14)=6$. Somit ist $14-\varphi (14)=14-6=8$.

Die Zahl $x_{3}=16$ ist zu den Zahlen $1,3,5,7,9,11,13$ und $15$ teilerfremd, es gibt also acht zu $x_{3}=16$ teilerfremde Zahlen und es ist $\varphi (16)=8$. Somit ist $16-\varphi (16)=16-8=8$.

Es gibt keine andere natürliche Zahl $k>1$, welche kleiner als $n=8$ ist, für welche die Gleichung $x-\varphi (x)=k$ drei oder mehr Lösungen hat. Somit ist $n=8$ eine hochkototiente Zahl.

Mit anderen Worten: es gibt genau drei Zahlen, nämlich $x_{1}=12$, $x_{2}=14$ und $x_{3}=16$, deren Kototient $n=8$ ist. Die Anzahl der Zahlen, deren Kototient $n<8$ ist, darf jeweils nicht größer oder gleich $3$ sein. Da dies der Fall ist, ist $n=8$ eine hochkototiente Zahl.

Tatsächlich kommt in der obigen Liste der Kototienten der Wert $8$ nur drei Mal vor, nämlich an der 12., an der 14. und an der 16. Stelle.

• Die ersten hochkototienten Zahlen sind die folgenden:

2, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 119, 167, 209, 269, 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889, 2099, 2309, 2729, 3149, 3359, 3569, 3989, 4199, 4289, 4409, 4619, 5249, 5459, 5879, 6089, 6509, 6719, 6929 … (Folge A100827 in OEIS)

Die Zahlen dieser Liste werden definitionsbedingt immer größer (im Gegensatz zur Liste, die im nächsten Beispiel steht).

Diese oberen hochkototienten Zahlen sind die Kototienten für $k$ Zahlen (aufsteigend für $k=0,1,2,3,\ldots$):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 19, 20, 22, 25, 28, 31, 34, 41, 42, 46, 52, 58, 59, 69, 74, 77, 83, 93, 99, 116, 130, 138, 140, 156, 165, 166, 167, 173, 192, 200, 218, 219, 223, 241, 242, 271, 276, 292, 304, 331 … (Folge A101373 in OEIS)

Beispiel:

An der 12. Stelle der ersten Liste steht die Zahl $n=119$. An der 12. Stelle der unteren Liste steht die Zahl $k=13$. Das bedeutet, dass es $13$ verschiedene Zahlen gibt, deren Kototient $n=119$ ergibt. Keine andere Zahl kleiner als $119$ ist der Kototient von gleich viel oder mehr als $13$ verschiedenen Zahlen, was $n=119$ zur hochkototienten Zahl macht.

• Die nächste Liste gibt die kleinsten Zahlen an, welche Kototient für $k$ Zahlen sind (aufsteigend für $k=0,1,2,3,\ldots$):

10, 0, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 143, 119, 197, 167, 279, 233, 281, 209, 269, 323, 299, 359, 497, 329, 455, 605, 389, 461, 479, 419, 539, 599, 509, 755, 791, 713, 875, 797, 719, 629, 659, 1025, 1163, 929, 779, 1193, 1121, 899, 1133, 1091, 839 … (Folge A063741 in OEIS)

Diese Liste ähnelt sehr der vorigen Liste der hochkototienten Zahlen, es können die Zahlen aber im Gegensatz zur vorigen Liste der hochkototienten Zahlen auch wieder kleiner werden.

Beispiel 1:

An der $k=0$-ten Stelle steht die Zahl $n=10$. Es gibt keine Zahl $x$, für welche $x-\varphi (x)=10$ lösbar wäre. Somit hat keine Zahl $x$ den Kototienten $n=10$. Zahlen $n$, für welche es keine Zahlen $x$ gibt, für welche $x-\varphi (x)=n$ lösbar wäre, nennt man Nichtkototient (vom englischen Noncototient). Die kleinsten Nichtkototienten lauten:

10, 26, 34, 50, 52, 58, 86, 100, 116, 122 … (Folge A005278 in OEIS)

Beispiel 2:

An der $k=12$-ten Stelle (wenn man mit $k=0$ zu zählen beginnt) steht die Zahl $n=143$. Es gibt somit $12$ Zahlen, deren Kototient $n=143$ ist und es gibt kein $n<143$, welche ebenfalls Kototient für $12$ Zahlen wäre. Somit ist $n=143$ der kleinste Wert, für den es $12$ Zahlen gibt, die alle denselben Kototient, nämlich $n=143$, haben.

Vergleicht man diesen Wert aber mit der Liste der hochkototienten Zahlen direkt darüber, dann stellt man fest, dass dort an der $k=12$-ten Stelle die Zahl $n=119$ steht. Diese Zahl ist der Kototient von $13$ verschiedenen Zahlen, die alle denselben Kototient, nämlich $n=119$, haben. Weil es keinen kleineren Wert $n<119$ gibt, der Kototient für $13$ oder mehr Zahlen ist, ist $n=119$ eine hochkototiente Zahl. Der Wert $n=143$ ist zwar der kleinste Wert, der Kototient von $12$ verschiedenen Zahlen ist, da er aber größer als $119$ ist, ist er nicht hochkototient und kommt deswegen in dieser Liste nicht vor.

• Es folgt eine Tabelle, von der man etwas leichter die hochkototienten Zahlen 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 höhere Zahl steht als in allen anderen Zeilen zuvor (außer bei $n=1$), handelt es sich bei $n$ um eine hochkototiente Zahl (welche gelb eingefärbt wird). Am Ende der Tabelle werden noch ein paar ausgewählte weitere $n$ angeführt, die in obigen Beispielen eventuell auftauchen:

Tabelle der Kototienten

$n$	$k$, sodass $k-\varphi (k)=n$	Anzahl der $k$, sodass $k-\varphi (k)=n$ (Folge A063740 in OEIS)
000	1	1
001	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 … (alle Primzahlen)	∞
002	4	1
003	9	1
004	6, 8	2
005	25	1
006	10	1
007	15, 49	2
008	12, 14, 16	3
009	21, 27	2
010		0
011	35, 121	2
012	18, 20, 22	3
013	33, 169	2
014	26	1
015	39, 55	2
016	24, 28, 32	3
017	65, 77, 289	3
018	34	1
019	51, 91, 361	3
020	38	1
021	45, 57, 85	3
022	30	1
023	95, 119, 143, 529	4
024	36, 40, 44, 46	4
025	69, 125, 133	3
026		0
027	63, 81, 115, 187	4
028	52	1
029	161, 209, 221, 841	4
030	42, 50, 58	3
031	87, 247, 961	3
032	48, 56, 62, 64	4
033	93, 145, 253	3
034		0
035	75, 155, 203, 299, 323	5
036	54, 68	2
037	217, 1369	2
038	74	1
039	99, 111, 319, 391	4
040	76	1
041	185, 341, 377, 437, 1681	5
042	82	1
043	123, 259, 403, 1849	4
044	60, 86	2
045	117, 129, 205, 493	4
046	66, 70	2
047	215, 287, 407, 527, 551, 2209	6
048	72, 80, 88, 92, 94	5
049	141, 301, 343, 481, 589	5
050		0
…	…	…
059	371, 611, 731, 779, 851, 899, 3481	7
063	135, 147, 171, 183, 295, 583, 799, 943	8
083	395, 803, 923, 1139, 1403, 1643, 1739, 1763, 6889	9
089	581, 869, 1241, 1349, 1541, 1769, 1829, 1961, 2021, 7921	10
113	545, 749, 1133, 1313, 1649, 2573, 2993, 3053, 3149, 3233, 12769	11
119	539, 791, 1199, 1391, 1751, 1919, 2231, 2759, 3071, 3239, 3431, 3551, 3599	13
143	363, 695, 959, 1703, 2159, 3503, 3959, 4223, 4343, 4559, 5063, 5183 (erstmaliges Auftreten von 12 Werten)	12
167	455, 815, 1727, 2567, 2831, 4031, 4247, 4847, 5207, 6431, 6527, 6767, 6887, 7031, 27889	15
197	965, 1337, 3077, 3401, 5177, 6437, 7097, 8201, 8357, 8777, 9017, 9701, 9797, 38809 (erstmaliges Auftreten von 14 Werten)	14
209	2189, 2561, 3281, 3629, 5249, 5549, 6401, 7181, 7661, 8321, 8909, 9089, 9869, 10001, 10349, 10541, 10961, 11009, 11021	19
233	665, 1145, 1589, 2453, 4853, 7289, 7913, 8213, 9593, 10553, 11189, 11573, 12533, 13289, 13493, 13589, 54289 (erstmaliges Auftreten von 17 Werten)	17
269	1841, 3341, 4769, 6989, 7409, 8621, 9389, 9761, 10481, 12449, 14129, 14381, 15089, 16109, 16781, 17201, 17441, 17741, 18209, 72361	20
279	663, 783, 831, 2959, 4471, 5911, 7279, 9799, 10951, 12031, 16351, 16999, 18079, 18511, 18871, 19519 (erstmaliges Auftreten von 16 Werten)	16
281	1001, 1385, 2981, 3497, 4997, 7781, 9881, 10277, 12137, 13157, 14981, 16517, 17177, 18281, 18437, 18857, 19781, 78961 (erstmaliges Auftreten von 18 Werten)	18
299	1859, 2051, 4811, 5339, 6371, 7859, 8339, 9731, 11051, 14219, 14579, 15611, 16259, 16571, 18779, 20099, 20291, 20651, 20819, 21971, 22331, 22499	22
323	867, 2219, 3443, 4043, 5219, 9083, 11603, 12083, 13019, 14363, 16043, 17219, 18323, 20003, 22019, 22523, 23843, 25019, 25283, 26123, 26219 (erstmaliges Auftreten von 21 Werten)	21

Hochkototiente Primzahlen

• Die kleinsten hochkototienten Primzahlen sind die folgenden:

  2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839, 1049, 1259, 1889, 2099, 2309, 2729, 3359, 3989, 4289, 4409, 5879, 6089, 6719, 9029, 9239, 10289, 10709, 11549, 13649, 13859, 15329, 15959, 20789, 21839, 23099, 25409, 27299, 30029, … (Folge A105440 in OEIS)

Eigenschaften

• Es gibt unendlich viele hochkototiente Zahlen. Es sind aber nur 229 hochkototiente Zahlen bekannt (Stand: 23. Februar 2020).
• Unter den bekannten 229 hochkototienten Zahlen sind nur die ersten drei, nämlich $n_{1}=2$, $n_{2}=4$ und $n_{3}=8$ gerade Zahlen. Alle anderen sind ungerade Zahlen.
• Von den bekannten 229 hochkototienten Zahlen enden alle zwischen der 14. und der 229. hochkototienten Zahl mit der Ziffer 9. Es gilt also für alle diese hochkototienten Zahlen $n$ von $n_{14}=209$ bis $n_{229}=6276269$:

$n\equiv 9\equiv -1{\pmod {10}}$

• Von den bekannten 229 hochkototienten Zahlen ergeben alle zwischen der 9. und der 229. hochkototienten Zahl bei Division durch 6 einen Rest von 5. Es gilt also für alle diese hochkototienten Zahlen $n$ von $n_{9}=83$ bis $n_{229}=6276269$:

$n\equiv 5\equiv -1{\pmod {6}}$

• Von den bekannten 229 hochkototienten Zahlen ergeben alle zwischen der 14. und der 229. hochkototienten Zahl bei Division durch 30 einen Rest von 29. Es gilt also für alle diese hochkototienten Zahlen $n$ von $n_{14}=209$ bis $n_{229}=6276269$:

$n\equiv 29\equiv -1{\pmod {30}}$

• Von den bekannten 229 hochkototienten Zahlen ergeben alle zwischen der 41. und der 229. hochkototienten Zahl bei Division durch 210 einen Rest von 209. Es gilt also für alle diese hochkototienten Zahlen $n$ von $n_{41}=4409$ bis $n_{229}=6276269$:

$n\equiv 209\equiv -1{\pmod {210}}$

• Von den bekannten 229 hochkototienten Zahlen ergeben alle zwischen der 169. und der 229. hochkototienten Zahl bei Division durch 2310 einen Rest von 2309. Es gilt also für alle diese hochkototienten Zahlen $n$ von $n_{169}=1351349$ bis $n_{229}=6276269$:

$n\equiv 2309\equiv -1{\pmod {2310}}$

• Wenn man die obigen Ergebnisse zusammenfasst, erhält man folgendes Ergebnis:

Mit Ausnahme der ersten drei hochkototienten Zahlen $n_{1}=2$, $n_{2}=4$ und $n_{3}=8$ sind alle weiteren bekannten hochkototienten Zahlen kongruent -1 modulo einer Primfakultät.

Beispiel:

Die ersten Primfakultäten lauten $2\#=2$, $3\#=6$, $5\#=30$, $7\#=210$ und $11\#=2310$.

Die 200. hochkototiente Zahl ist $n_{200}=2984519$. Tatsächlich ist $n_{200}\equiv 2309\equiv -1{\pmod {2310}}$. Es ist auch $n_{200}\equiv 209\equiv -1{\pmod {210}}$, $n_{200}\equiv 29\equiv -1{\pmod {30}}$, $n_{200}\equiv 5\equiv -1{\pmod {6}}$ und $n_{200}\equiv 1\equiv -1{\pmod {2}}$.

Siehe auch

• Eulersche Phi-Funktion
• Hochtotiente Zahl
• Hochzusammengesetzte Zahl
• Nichtkototient
• Nichttotient
• Perfekt totiente Zahl
• Spärlich totiente Zahl

Weblinks

• Eric W. Weisstein: Highly Cototient Number. 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 15. Februar 2020 (deutsch). 

Einzelnachweise

V – D

Primzahl­mengen