Spärlich totiente Zahl
# Spärlich totiente Zahl

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

    $\varphi (m)>\varphi (k)$.

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

Diese Zahlen wurden von David Masser und Peter Shiu im Jahr 1986 erstmals erwähnt.

## Beispiele

* Die Totienten $\varphi (k)$, also die Anzahl der zu $k$ teilerfremden natürlichen Zahlen $x<k$, lauten (für $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 $4$. Die Zahl $k=8$ hat $4$ teilerfremde Zahlen, welche kleiner als $k=8$ sind, nämlich $1,3,5$ und $7$. Daher ist tatsächlich $\varphi (8)=4$.
             An der 7. Stelle obiger Liste steht die Zahl $6$. Die Zahl $k=7$ ist eine Primzahl und hat somit $6$ teilerfremde Zahlen, welche kleiner als $k=7$ sind, nämlich alle Zahlen von $1$ bis $6$. Somit ist $\varphi (7)=6$.
* Die Zahl $k=22$ ist keine spärlich totiente Zahl:

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

       Der Totient der Zahl $k=30$ ist $\varphi (30)=8$, weil zu $k=30$ genau $8$ teilerfremde Zahlen existieren, welche kleiner als $k=30$ sind (nämlich $x\in \{1,7,11,13,17,19,23,29\}$). Es gibt tatsächlich keine Zahl $m>30$, welche einen Totienten hat, der kleiner oder gleich $\varphi (30)=8$ ist. Somit ist $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 $n$, in der zweiten Spalte stehen diejenigen Zahlen, deren Totient $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 $n$ existieren bis auf $n=1$ nicht und werden deswegen weggelassen):

| $n$ | $k$, sodass $\varphi (k)=n$ | größtes $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 |
| $n$ | $k$, sodass $\varphi (k)=n$ | größtes $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 |
| $n$ | $k$, sodass $\varphi (k)=n$ | größtes $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 |
| $n$ | $k$, sodass $\varphi (k)=n$ | größtes $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.

       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 $k$, welche ungerade ist. Sei ihr Totient $\varphi (k)=n$. Es darf somit laut Definition der spärlich totienten Zahlen keine größere Zahl $m>k$ existieren, welche den gleichen Totienten $\varphi (m)=n=\varphi (k)$ hat (es müsste $\varphi (m)>n=\varphi (k)$ sein).
             Sei $m:=2k$. Weil die ungerade Zahl $k$ zu $2$ teilerfremd ist, und aufgrund der Rechenregeln der Eulerschen Phi-Funktion ist $\varphi (m)=\varphi (2k)=\varphi (2)\cdot \varphi (k)=1\cdot \varphi (k)=\varphi (k)=n$. Somit existiert eine größere, gerade Zahl $2k$, deren Totient $n$ ist. Damit kann $k$ keine spärlich totiente Zahl sein. Die Annahme, dass $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. $\Box$
* Sei $p\in \mathbb {P}$ eine ungerade Primzahl. Dann gilt:

       Jede Primfakultät $p\#$ und $p\cdot p\#$ ist eine spärlich totiente Zahl.
          Diesen Satz konnten David Masser und Peter Shiu beweisen.
