Perfekt totiente Zahl

Der Totient einer Zahl k {\displaystyle k} ist in der Zahlentheorie definiert als φ ( k ) {\displaystyle \varphi (k)} , welche auch Eulersche Phi-Funktion genannt wird und angibt, wie viele zu k {\displaystyle k} teilerfremde natürliche Zahlen x {\displaystyle x} es gibt, die nicht größer als k {\displaystyle k} sind.

Allgemeines

Eine perfekt totiente Zahl (englisch perfect totient number) ist eine natürliche Zahl n {\displaystyle n} , die man wie folgt erhält:

Man beginne mit der Zahl n {\displaystyle n} und bilde ihren Totienten φ ( n ) {\displaystyle \varphi (n)} . Nun bildet man von diesem Totienten φ ( n ) {\displaystyle \varphi (n)} den Totienten φ ( φ ( n ) ) {\displaystyle \varphi (\varphi (n))} und so fort, bis man den Wert 1 {\displaystyle 1} erreicht. Addiert man jetzt die so erhaltenen Totienten und erhält als Summe genau die Ausgangszahl n {\displaystyle n} , so ist n {\displaystyle n} eine perfekt totiente Zahl.

Mathematisch formuliert bedeutet das:

Sei φ i ( n ) := { φ ( n )  für  i = 1 φ ( φ i − 1 ( n ) )  sonst {\displaystyle \varphi ^{i}(n):=\left\{{\begin{matrix}\varphi (n)&{\mbox{ für }}i=1\\\varphi (\varphi ^{i-1}(n))&{\mbox{ sonst}}\end{matrix}}\right.}
für die iterierten Totienten.
Sei weiters c {\displaystyle c} eine natürliche Zahl mit φ c ( n ) = 2 {\displaystyle \varphi ^{c}(n)=2} .
Dann ist n {\displaystyle n} eine perfekt totiente Zahl, wenn gilt:
n = ∑ i = 1 c + 1 φ i ( n ) {\displaystyle n=\sum _{i=1}^{c+1}\varphi ^{i}(n)}

Diese Zahlen wurden erstmals vom Mathematiker Laureano Pérez-Cacho im Jahr 1939 untersucht.[1] Nach einer längeren Pause beschäftigte sich im Jahr 1975 der Mathematiker T. Venkataraman[2] und im Jahr 1982 die beiden Mathematiker A. L. Mohan und D. Suryanarayana mit diesen Zahlen.[3]

Beispiele

  • Sei n = 9 {\displaystyle n=9} .
Zur Zahl n = 9 {\displaystyle n=9} gibt es 6 {\displaystyle 6} teilerfremde Zahlen, welche kleiner als n = 9 {\displaystyle n=9} sind, nämlich 1 , 2 , 4 , 5 , 7 {\displaystyle 1,2,4,5,7} und 8 {\displaystyle 8} . Somit ist φ ( 9 ) = 6 {\displaystyle \varphi (9)=6} .
Nun bestimmt man den Totienten von 6 {\displaystyle 6} . Zur Zahl 6 {\displaystyle 6} gibt es nur 2 {\displaystyle 2} teilerfremde Zahlen, welche kleiner als 6 {\displaystyle 6} sind, nämlich 1 {\displaystyle 1} und 5 {\displaystyle 5} . Somit ist φ ( 6 ) = 2 {\displaystyle \varphi (6)=2} .
Bleibt noch die Bestimmung des Totienten von 2 {\displaystyle 2} . Zur Zahl 2 {\displaystyle 2} gibt es nur eine teilerfremde Zahl, welche kleiner als 2 {\displaystyle 2} ist, nämlich 1 {\displaystyle 1} . Somit ist φ ( 2 ) = 1 {\displaystyle \varphi (2)=1} .
Man erhält φ ( φ ( φ ( 9 ) ) ) = φ ( φ ( 6 ) ) = φ ( 2 ) = 1 {\displaystyle \varphi (\varphi (\varphi (9)))=\varphi (\varphi (6))=\varphi (2)=1} .
Addiert man nun die so erhaltenen Totienten, erhält man 6 + 2 + 1 = 9 = n {\displaystyle 6+2+1=9=n} , die Ausgangszahl. Also ist n = 9 {\displaystyle n=9} eine perfekt totiente Zahl.
  • Die folgenden Zahlen sind die kleinsten perfekt totienten Zahlen:
3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147, 208191, 441027, 531441, 1594323, 4190263, 4782969, 9056583, 14348907, 43046721, … (Folge A082897 in OEIS)
Es gibt 61 perfekt totiente Zahlen, welche kleiner als eine Billion (also kleiner als 10 12 {\displaystyle 10^{12}} ) sind.[4]

Eigenschaften

  • Jede perfekt totiente Zahl ist ungerade.
Beweis:
Eine Eigenschaft der Totienten ist, dass φ ( n ) {\displaystyle \varphi (n)} für n ≥ 3 {\displaystyle n\geq 3} immer eine gerade Zahl ergibt (nur φ ( 1 ) = φ ( 2 ) = 1 {\displaystyle \varphi (1)=\varphi (2)=1} ergibt einen ungeraden Totienten). Somit müssen bei der Kontrolle, ob eine Zahl eine perfekt totiente Zahl ist oder nicht, anfangs immer nur gerade Zahlen aufaddiert werden, was letztendlich als Summe wiederum eine gerade Zahl ergibt. Ganz zum Schluss muss aber zu dieser geraden Zahl noch φ ( 2 ) = 1 {\displaystyle \varphi (2)=1} , eine ungerade Zahl, hinzuaddiert werden, womit man als Gesamtsumme eine ungerade Zahl erhält. Diese Totienten-Gesamtsumme ist aber der Wert der perfekt totienten Zahl, woraus man folgern kann, dass alle perfekt totienten Zahlen ungerade sein müssen. ◻ {\displaystyle \Box }
  • Alle Zahlen der Form n = 3 k {\displaystyle n=3^{k}} mit k ∈ N {\displaystyle k\in \mathbb {N} } , k > 0 {\displaystyle k>0} , sind perfekte totiente Zahlen.
Beweis der Behauptung:
Beweis:
Es wird die folgende Rechenregel der Eulerschen Phi-Funktion verwendet: φ ( p k ) = p k − 1 ( p − 1 ) {\displaystyle \quad \varphi (p^{k})=p^{k-1}(p-1)}
Somit gilt:
φ ( 3 k ) = 3 k − 1 ⋅ ( 3 − 1 ) = 2 ⋅ 3 k − 1 {\displaystyle \varphi (3^{k})=3^{k-1}\cdot (3-1)=2\cdot 3^{k-1}}
Es wird auch die folgende Eigenschaft der Eulerschen Phi-Funktion für teilerfremde Zahlen m {\displaystyle m} und n {\displaystyle n} verwendet: φ ( m ⋅ n ) = φ ( m ) ⋅ φ ( n ) {\displaystyle \quad \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)}
Somit gilt, mit Einbeziehung der obigen beiden Regeln:
φ 2 ( 3 k ) = φ ( 2 ⋅ 3 k − 1 ) = φ ( 2 ) ⋅ φ ( 3 k − 1 ) = 1 ⋅ 2 ⋅ 3 k − 2 = 2 ⋅ 3 k − 2 {\displaystyle \varphi ^{2}(3^{k})=\varphi (2\cdot 3^{k-1})=\varphi (2)\cdot \varphi (3^{k-1})=1\cdot 2\cdot 3^{k-2}=2\cdot 3^{k-2}}
φ 3 ( 3 k ) = φ ( 2 ⋅ 3 k − 2 ) = φ ( 2 ) ⋅ φ ( 3 k − 2 ) = 1 ⋅ 2 ⋅ 3 k − 3 = 2 ⋅ 3 k − 3 {\displaystyle \varphi ^{3}(3^{k})=\varphi (2\cdot 3^{k-2})=\varphi (2)\cdot \varphi (3^{k-2})=1\cdot 2\cdot 3^{k-3}=2\cdot 3^{k-3}}
etc.
Der Beweis funktioniert mittels vollständiger Induktion.
Induktionsanfang: Die Aussage stimmt für k = 1 {\displaystyle k=1} :
Tatsächlich ist n = 3 k = 3 1 = 3 {\displaystyle n=3^{k}=3^{1}=3} eine perfekt totiente Zahl, weil φ ( 3 ) = 2 {\displaystyle \varphi (3)=2} , φ ( 2 ) = 1 {\displaystyle \varphi (2)=1} und 2 + 1 = 3 {\displaystyle 2+1=3} ist.
Die Induktionsvoraussetzung ist, dass n = 3 k − 1 {\displaystyle n=3^{k-1}} eine perfekt totiente Zahl ist, dass also gilt:
∑ i = 1 c + 1 φ i ( 3 k − 1 ) = φ ( 3 k − 1 ) + φ 2 ( 3 k − 1 ) + … + φ c + 1 ( 3 k − 1 ) = 2 ⋅ 3 k − 2 + 2 ⋅ 3 k − 3 + … + 2 ⋅ 3 2 + 2 ⋅ 3 1 + 2 ⋅ 3 0 + 1 = 1 + 2 + 2 ⋅ 3 + 2 ⋅ 9 + 2 ⋅ 27 + … + 2 ⋅ 3 k − 2 = ! 3 k − 1 {\displaystyle \sum _{i=1}^{c+1}\varphi ^{i}(3^{k-1})=\varphi (3^{k-1})+\varphi ^{2}(3^{k-1})+\ldots +\varphi ^{c+1}(3^{k-1})=2\cdot 3^{k-2}+2\cdot 3^{k-3}+\ldots +2\cdot 3^{2}+2\cdot 3^{1}+2\cdot 3^{0}+1={\color {red}1+2+2\cdot 3+2\cdot 9+2\cdot 27+\ldots +2\cdot 3^{k-2}\;{\stackrel {!}{=}}\;3^{k-1}}}
Nun kommt der Induktionsschluss: Es bleibt zu zeigen, dass auch n = 3 k {\displaystyle n=3^{k}} eine perfekt totiente Zahl ist.
Da 3 k − 1 {\displaystyle 3^{k-1}} laut Induktionsvoraussetzung eine perfekt totiente Zahl ist, muss gelten:
∑ i = 1 c + 1 φ i ( 3 k ) = φ ( 3 k ) + φ 2 ( 3 k ) + φ 3 ( 3 k ) + … + φ c ( 3 k ) + φ c + 1 ( 3 k ) = φ c + 1 ( 3 k ) + φ c ( 3 k ) + … + φ 3 ( 3 k ) + φ 2 ( 3 k ) + φ ( 3 k ) = 1 + 2 ⋅ 3 0 + 2 ⋅ 3 1 + 2 ⋅ 3 2 + … + 2 ⋅ 3 k − 3 + 2 ⋅ 3 k − 2 + 2 ⋅ 3 k − 1 = 1 + 2 + 2 ⋅ 3 + 2 ⋅ 9 + 2 ⋅ 27 + … + 2 ⋅ 3 k − 2 + 2 ⋅ 3 k − 1 = 3 k − 1 + 2 ⋅ 3 k − 1 (Induktionsvoraussetzung) = 3 ⋅ 3 k − 1 = 3 k {\displaystyle {\begin{array}{rcl}\displaystyle \sum _{i=1}^{c+1}\varphi ^{i}(3^{k})&=&\varphi (3^{k})+\varphi ^{2}(3^{k})+\varphi ^{3}(3^{k})+\ldots +\varphi ^{c}(3^{k})+\varphi ^{c+1}(3^{k})\\&=&\varphi ^{c+1}(3^{k})+\varphi ^{c}(3^{k})+\ldots +\varphi ^{3}(3^{k})+\varphi ^{2}(3^{k})+\varphi (3^{k})\\&=&1+2\cdot 3^{0}+2\cdot 3^{1}+2\cdot 3^{2}+\ldots +2\cdot 3^{k-3}+2\cdot 3^{k-2}+2\cdot 3^{k-1}\\&=&{\color {red}1+2+2\cdot 3+2\cdot 9+2\cdot 27+\ldots +2\cdot 3^{k-2}}+2\cdot 3^{k-1}\\&=&{\color {red}3^{k-1}}+2\cdot 3^{k-1}\qquad {\text{(Induktionsvoraussetzung)}}\\&=&3\cdot 3^{k-1}\\&=&3^{k}\end{array}}}
Damit ergibt die Summe der jeweiligen Totienten genau 3 k {\displaystyle 3^{k}} , somit ist 3 k {\displaystyle 3^{k}} eine perfekt totiente Zahl. Was zu beweisen war. ◻ {\displaystyle \Box }
  • Die meisten der bekannten perfekt totienten Zahlen sind Vielfache von Potenzen von 3 {\displaystyle 3} , also von der Form n = x ⋅ 3 k {\displaystyle n=x\cdot 3^{k}} . Die kleinste perfekt totiente Zahl, die nicht durch 3 {\displaystyle 3} teilbar ist, ist n = 4375 {\displaystyle n=4375} .[5]
  • Sei n i {\displaystyle n_{i}} die i {\displaystyle i} -te perfekt totiente Zahl. Für die ersten 64 bekannten perfekt totienten Zahlen gilt:[6]
n i ≈ 1 , 56 i {\displaystyle n_{i}\approx 1,56^{i}}
  • Das Produkt der ersten n {\displaystyle n} Fermat-Primzahlen ist eine perfekt totiente Zahl.[6]
Beispiele:
Im Moment sind nur die fünf Fermat-Primzahlen 3 , 5 , 17 , 257 {\displaystyle 3,5,17,257} und 65537 {\displaystyle 65537} bekannt. Multipliziert man sie miteinander, erhält man die Zahlen 3 , 15 , 255 , 65535 {\displaystyle 3,15,255,65535} und 4294967295 {\displaystyle 4294967295} , welche tatsächlich allesamt perfekt totiente Zahlen sind.
  • Sei n := 3 p {\displaystyle n:=3p} mit primen p ∈ P {\displaystyle p\in \mathbb {P} } , p > 3 {\displaystyle p>3} . Dann gilt:[1][7]
n {\displaystyle n} ist eine perfekt totiente Zahl genau dann, wenn p = 4 k + 1 {\displaystyle p=4k+1} und k {\displaystyle k} ist selbst eine perfekt totiente Zahl.
Dieser Satz konnte schon im Jahr 1939 von L. P. Cacho bewiesen werden.
Beispiel:
Die Zahl k = 9 {\displaystyle k=9} ist eine perfekt totiente Zahl. Es ist p = 4 k + 1 = 4 ⋅ 9 + 1 = 37 {\displaystyle p=4k+1=4\cdot 9+1=37} eine Primzahl. Man erhält die Zahl n = 3 p = 3 ⋅ 37 = 111 {\displaystyle n=3p=3\cdot 37=111} , welche tatsächlich eine perfekt totiente Zahl ist.
  • Sei p := 4 ⋅ 3 k + 1 {\displaystyle p:=4\cdot 3^{k}+1} eine Primzahl mit natürlichem k > 0 {\displaystyle k>0} . Dann gilt:[2][8]
n = 3 p {\displaystyle n=3p} ist eine perfekt totiente Zahl.
Dieser Satz wurde vom Mathematiker T. Venkataraman im Jahr 1975 bewiesen.
Die folgende Liste gibt die kleinsten k {\displaystyle k} an, für welche Zahlen der Form p = 4 ⋅ 3 k + 1 {\displaystyle p=4\cdot 3^{k}+1} Primzahlen sind:
0, 1, 2, 3, 6, 14, 15, 39, 201, 249, 885, 1005, 1254, 1635, 3306, 3522, 9602, 19785, 72698, 233583, 328689, 537918, 887535, 980925, 1154598, 1499606, … (Folge A005537 in OEIS)
  • Sei n := 3 p {\displaystyle n:=3p} mit primen p ∈ P {\displaystyle p\in \mathbb {P} } , p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3{\pmod {4}}} . Dann gilt:[9]
n {\displaystyle n} ist keine perfekt totiente Zahl.
Dieser Satz wurde von den beiden Mathematikern A. L. Mohan und D. Suryanarayana im Jahr 1982 bewiesen.

Siehe auch

Literatur

  • A. L. Mohan, D. Suryanarayana: Perfect totient numbers. In: Krishnaswami Alladi (Hrsg.): Number Theory (= Lecture Notes in Mathematics. Band 938). Springer, Berlin/Heidelberg 1982, ISBN 978-3-540-11568-7, S. 101–105, doi:10.1007/BFb0097177 (englisch). 
  • Jozsef Sándor, Borislav Crstici: Handbook of Number Theory II. Kluwer Academic Publishers, Dordrecht/Boston/London 2004, ISBN 1-4020-2546-7, Abschnitt „Perfect totient numbers and related results“, S. 240–242 (englisch, Online [abgerufen am 28. März 2020]). 
  • T. Venkataraman: Perfect totient number. The Mathematics Student 43, 1975, S. 178, abgerufen am 25. März 2020. 
  • Douglas E. Iannucci, Deng Moujie, Graeme L. Cohen: On Perfect Totient Numbers. (PDF). Journal of Integer Sequences 6, Article 03.4.5, 2003, S. 1–7, abgerufen am 25. März 2020. 
  • Florian Luca: On the Distribution of Perfect Totients. (PDF). Journal of Integer Sequences 9, Article 06.4.4, 2006, S. 1–17, abgerufen am 25. März 2020. 
  • Igor E. Shparlinski: On the Sum of Iterations of the Euler Function. Journal of Integer Sequences 9, Article 06.1.6, 2006, S. 1–5, abgerufen am 25. März 2020. 
  • Paul Loomis, Michael Plytage & John Polhill: Summing Up the Euler φ Function. The College Mathematics Journal 39 (1), Januar 2008, S. 34–42, abgerufen am 25. März 2020. 
  • perfect totient number. In: PlanetMath. (englisch)
  • Perfect totient numbers. Programmcodes für perfekt totiente Zahlen. Rosettacode.org, 14. März 2020, abgerufen am 25. März 2020. 

Einzelnachweise

  1. ↑ a b Laureano Pérez-Cacho (1939). "Sobre la suma de indicadores de ordenes sucesivos". Revista Matematica Hispano-Americana. 5 (3): S. 45–50.
  2. ↑ a b T. Venkataraman: Perfect totient number. The Mathematics Student 43, 1975, S. 178, abgerufen am 25. März 2020. 
  3. ↑ A. L. Mohan, D. Suryanarayana: Perfect Totient Numbers. Springer, Berlin, Heidelberg, 1982, S. 101–105, abgerufen am 25. März 2020. 
  4. ↑ Liste der ersten 64 perfekt totienten Zahlen auf OEIS A082897
  5. ↑ Robert Munafo: Sequence A082897: Perfect Totient Numbers. 2020, abgerufen am 25. März 2020. 
  6. ↑ a b Comments zu OEIS A082897
  7. ↑ A. L. Mohan, D. Suryanarayana: Perfect Totient Numbers. Remark 1. Springer, Berlin, Heidelberg, 1982, S. 101, abgerufen am 25. März 2020. 
  8. ↑ Douglas E. Iannucci, Deng Moujie, Graeme L. Cohen: On Perfect Totient Numbers. (PDF), Information vor der Tafel auf S. 2. Journal of Integer Sequences 6, Article 03.4.5, 2003, S. 1–7, abgerufen am 25. März 2020. 
  9. ↑ A. L. Mohan, D. Suryanarayana: Perfect Totient Numbers. Theorem 1. Springer, Berlin, Heidelberg, 1982, S. 101, abgerufen am 25. März 2020.