Spärlich totiente Zahl

Der Totient einer Zahl ${\displaystyle k}$ ist in der Zahlentheorie definiert als ${\displaystyle \varphi (k)}$, welche auch Eulersche Phi-Funktion genannt wird und angibt, wie viele zu ${\displaystyle k}$ teilerfremde natürliche Zahlen ${\displaystyle x}$ es gibt, die nicht größer als ${\displaystyle k}$ sind. Eine spärlich totiente Zahl (vom englischen sparsely totient number) ist eine natürliche Zahl ${\displaystyle k}$, für welche für alle ${\displaystyle m>k}$ gilt:

${\displaystyle \varphi (m)>\varphi (k)}$.

Mit anderen Worten: Wenn die Totienten ${\displaystyle \varphi (m)}$ von allen Zahlen ${\displaystyle m>k}$ größer sind als der Totient von ${\displaystyle k}$, so ist ${\displaystyle k}$ eine spärlich totiente Zahl.

Diese Zahlen wurden v​on David Masser u​nd Peter Shiu i​m Jahr 1986 erstmals erwähnt.[1][2]

Beispiele

• Die Totienten ${\displaystyle \varphi (k)}$, also die Anzahl der zu ${\displaystyle k}$ teilerfremden natürlichen Zahlen ${\displaystyle x<k}$, lauten (für ${\displaystyle k=1,2,3,\ldots }$):

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, … (Folge A000010 in OEIS)

Beispiel:

An der 8. Stelle obiger Liste steht die Zahl ${\displaystyle 4}$. Die Zahl ${\displaystyle k=8}$ hat ${\displaystyle 4}$ teilerfremde Zahlen, welche kleiner als ${\displaystyle k=8}$ sind, nämlich ${\displaystyle 1,3,5}$ und ${\displaystyle 7}$. Daher ist tatsächlich ${\displaystyle \varphi (8)=4}$.

An der 7. Stelle obiger Liste steht die Zahl ${\displaystyle 6}$. Die Zahl ${\displaystyle k=7}$ ist eine Primzahl und hat somit ${\displaystyle 6}$ teilerfremde Zahlen, welche kleiner als ${\displaystyle k=7}$ sind, nämlich alle Zahlen von ${\displaystyle 1}$ bis ${\displaystyle 6}$. Somit ist ${\displaystyle \varphi (7)=6}$.

• Die Zahl ${\displaystyle k=22}$ ist keine spärlich totiente Zahl:

Der Totient der Zahl ${\displaystyle k=22}$ ist ${\displaystyle \varphi (22)=10}$, weil zu ${\displaystyle k=22}$ genau ${\displaystyle 10}$ teilerfremde Zahlen existieren, welche kleiner als ${\displaystyle k=22}$ sind (nämlich ${\displaystyle x\in \{1,3,5,7,9,13,15,17,19,21\}}$). Für alle größeren Zahlen ${\displaystyle m>22}$ müsste ${\displaystyle \varphi (m)>\varphi (22)}$ gelten. Dies ist aber nicht der Fall, weil zum Beispiel die Zahl ${\displaystyle k=24}$ genau ${\displaystyle 8}$ teilerfremde Zahlen hat (nämlich ${\displaystyle x\in \{1,5,7,11,13,17,19,23\}}$), es ist also ${\displaystyle \varphi (24)=8<10=\varphi (22)}$, womit die Voraussetzung für spärlich totiente Zahlen nicht erfüllt ist.

• Die Zahl ${\displaystyle k=30}$ ist eine spärlich totiente Zahl:

Der Totient der Zahl ${\displaystyle k=30}$ ist ${\displaystyle \varphi (30)=8}$, weil zu ${\displaystyle k=30}$ genau ${\displaystyle 8}$ teilerfremde Zahlen existieren, welche kleiner als ${\displaystyle k=30}$ sind (nämlich ${\displaystyle x\in \{1,7,11,13,17,19,23,29\}}$). Es gibt tatsächlich keine Zahl ${\displaystyle m>30}$, welche einen Totienten hat, der kleiner oder gleich ${\displaystyle \varphi (30)=8}$ ist. Somit ist ${\displaystyle k=30}$ eine spärlich totiente Zahl.

• Die folgenden Zahlen sind die kleinsten spärlich totienten Zahlen:

2, 6, 12, 18, 30, 42, 60, 66, 90, 120, 126, 150, 210, 240, 270, 330, 420, 462, 510, 630, 660, 690, 840, 870, 1050, 1260, 1320, 1470, 1680, 1890, 2310, 2730, 2940, 3150, 3570, 3990, 4620, 4830, 5460, 5610, 5670, 6090, 6930, 7140, 7350, 8190, 9240, 9660, … (Folge A036913 in OEIS)

• Es folgt eine Tabelle, von der man etwas leichter die spärlich totienten Zahlen ablesen kann. In der ersten Spalte sind die aufsteigenden Totienten ${\displaystyle n}$, in der zweiten Spalte stehen diejenigen Zahlen, deren Totient ${\displaystyle n}$ ist und in der dritten Spalte kann man den größten Wert der zweiten Spalte ablesen. Ist diese Zahl größer als alle vorherigen Werte, so handelt es sich um eine spärlich totiente Zahl und wird gelb eingefärbt (ungerade Totienten ${\displaystyle n}$ existieren bis auf ${\displaystyle n=1}$ nicht und werden deswegen weggelassen):

Tabelle der Totienten

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle \varphi (k)=n}$ größtes ${\displaystyle k}$ der vorigen Spalte (Folge A006511 in OEIS) 1 1, 2 2 2 3, 4, 6 6 4 5, 8, 10, 12 12 6 7, 9, 14, 18 18 8 15, 16, 20, 24, 30 30 10 11, 22 22 12 13, 21, 26, 28, 36, 42 42 14 - 16 17, 32, 34, 40, 48, 60 60 18 19, 27, 38, 54 54 20 25, 33, 44, 50, 66 66 22 23, 46 46 24 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 90 26 - 28 29, 58 58 30 31, 62 62 32 51, 64, 68, 80, 96, 102, 120 120 34 - 36 37, 57, 63, 74, 76, 108, 114, 126 126

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle \varphi (k)=n}$ größtes ${\displaystyle k}$ der vorigen Spalte (Folge A006511 in OEIS) 38 - 40 41, 55, 75, 82, 88, 100, 110, 132, 150 150 42 43, 49, 86, 98 98 44 69, 92, 138 138 46 47, 94 94 48 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 210 50 - 52 53, 106 106 54 81, 162 162 56 87, 116, 174 174 58 59, 118 118 60 61, 77, 93, 99, 122, 124, 154, 186, 198 198 62 - 64 85, 128, 136, 160, 170, 192, 204, 240 240 66 67, 134 134 68 - 70 71, 142 142 72 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 270

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle \varphi (k)=n}$ größtes ${\displaystyle k}$ der vorigen Spalte (Folge A006511 in OEIS) 74 - 76 - 78 79, 158 158 80 123, 164, 165, 176, 200, 220, 246, 264, 300, 330 330 82 83, 166 166 84 129, 147, 172, 196, 258, 294 294 86 - 88 89, 115, 178, 184, 230, 276 276 90 - 92 141, 188, 282 282 94 - 96 97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420 420 98 - 100 101, 125, 202, 250 250 102 103, 206 206 104 159, 212, 318 318 106 107, 214 214 108 109, 133, 171, 189, 218, 266, 324, 342, 378 378

${\displaystyle n}$ ${\displaystyle k}$, sodass ${\displaystyle \varphi (k)=n}$ größtes ${\displaystyle k}$ der vorigen Spalte (Folge A006511 in OEIS) 110 121, 242 242 112 113, 145, 226, 232, 290, 348 348 114 - 116 177, 236, 354 354 118 - 120 143, 155, 175, 183, 225, 231, 244, 248, 286, 308, 310, 350, 366, 372, 396, 450, 462 462 122 - 124 - 126 127, 254 254 128 255, 256, 272, 320, 340, 384, 408, 480, 510 510 130 131, 262 262 132 161, 201, 207, 268, 322, 402, 414 414 134 - 136 137, 274 274 138 139, 278 278 140 213, 284, 426 426 142 - 144 185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630 630

Eigenschaften

• Jede spärlich totiente Zahl ist eine gerade Zahl.[3]

Beweis:

Der Beweis ist ein Beweis durch Widerspruch, es wird eine Annahme getätigt, welche sich im Laufe des Beweises als falsch erweist. Die Annahme muss fallengelassen werden und das Gegenteil der Annahme muss stimmen:

Angenommen, es gibt eine spärlich totiente Zahl ${\displaystyle k}$, welche ungerade ist. Sei ihr Totient ${\displaystyle \varphi (k)=n}$. Es darf somit laut Definition der spärlich totienten Zahlen keine größere Zahl ${\displaystyle m>k}$ existieren, welche den gleichen Totienten ${\displaystyle \varphi (m)=n=\varphi (k)}$ hat (es müsste ${\displaystyle \varphi (m)>n=\varphi (k)}$ sein).

Sei ${\displaystyle m:=2k}$. Weil die ungerade Zahl ${\displaystyle k}$ zu ${\displaystyle 2}$ teilerfremd ist, und aufgrund der Rechenregeln der Eulerschen Phi-Funktion ist ${\displaystyle \varphi (m)=\varphi (2k)=\varphi (2)\cdot \varphi (k)=1\cdot \varphi (k)=\varphi (k)=n}$. Somit existiert eine größere, gerade Zahl ${\displaystyle 2k}$, deren Totient ${\displaystyle n}$ ist. Damit kann ${\displaystyle k}$ keine spärlich totiente Zahl sein. Die Annahme, dass ${\displaystyle k}$ eine ungerade spärlich totiente Zahl ist, muss fallengelassen werden, es gibt also keine ungeraden spärlich totienten Zahlen, es müssen spärlich totiente Zahlen allesamt gerade sein. ${\displaystyle \Box }$

• Sei ${\displaystyle p\in \mathbb {P} }$ eine ungerade Primzahl. Dann gilt:[1][4]

Jede Primfakultät ${\displaystyle p\#}$ und ${\displaystyle p\cdot p\#}$ ist eine spärlich totiente Zahl.

Diesen Satz konnten David Masser und Peter Shiu beweisen.

Siehe auch

• Eulersche Phi-Funktion
• Hochkototiente Zahl
• Hochtotiente Zahl
• Hochzusammengesetzte Zahl
• Nichtkototient
• Nichttotient
• Perfekt totiente Zahl

Weblinks

• David Masser, Peter Shiu: On sparsely totient numbers. Pac. J. Math. 121, 1986, S. 407–426, abgerufen am 1. März 2020.
• Roger C. Baker, Glyn Harman: Sparsely totient numbers. Ann. Fac. Sci. Toulouse, VI. Sér., Math. 5 (2), 1996, S. 183–190, abgerufen am 1. März 2020.

Einzelnachweise

1. David Masser, Peter Shiu: On sparsely totient numbers. Theorem 1. Pac. J. Math. 121, 1986, S. 407–426, abgerufen am 1. März 2020.
2. Roger C. Baker, Glyn Harman: Sparsely totient numbers. Theorem. Ann. Fac. Sci. Toulouse, VI. Sér., Math. 5 (2), 1996, S. 183–190, abgerufen am 1. März 2020.
3. Comments zu OEIS A006511
4. Comments zu OEIS A036913