Nichttotient

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der Zahlentheorie ist der Totient einer natürlichen Zahl definiert als die Anzahl der zu teilerfremden natürlichen Zahlen, die nicht größer als sind. wird auch eulersche Phi-Funktion genannt. Ein Nichttotient (vom englischen Nontotient) ist eine natürliche Zahl , die kein Totient ist, also eine Zahl, für die Gleichung

keine Lösung für hat. Mit anderen Worten: Eine natürliche Zahl ist ein Nichttotient, wenn es keine natürliche Zahl gibt, zu der es exakt teilerfremde Zahlen gibt.

  • Die Zahl ist ein Nichttotient, weil es keine natürliche Zahl gibt, für welche exakt teilerfremde Zahlen existieren, die kleiner als sind.
  • Die Zahl ist kein Nichttotient:
Die Primzahl ist zu Zahlen teilerfremd, somit ist auch . Die Gleichung hat also mindestens eine Lösung , also ist kein Nichttotient. Weitere muss man nicht suchen (obwohl auch die Zahlen , und den Totienten hätten).
  • Die Zahl ist kein Nichttotient:
Die Zahl ist als Sonderfall des leeren Produkts (weder Primzahl noch zusammengesetzte Zahl) auch zu sich selbst teilerfremd, also ist . Außerdem ist die Zahl zu teilerfremd, somit ist auch . Somit hat die Gleichung sogar zwei Lösungen und , also ist kein Nichttotient.
  • Die folgenden Zahlen sind die kleinsten geraden Nichttotienten:
14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, 302, 304, 308, 314, 318, … (Folge A005277 in OEIS)
  • Die nächste Liste gibt die kleinsten an, deren Totient ist (für aufsteigende )
1, 3, 0, 5, 0, 7, 0, 15, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 25, 0, 23, 0, 35, 0, 0, 0, 29, 0, 31, 0, 51, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 69, 0, 47, 0, 65, 0, 0, 0, 53, 0, 81, 0, 87, 0, 59, 0, 61, 0, 0, 0, 85, 0, 67, 0, 0, 0, 71, 0, 73, 0, 0, 0, 0, 0, 79, 0, 123, 0, 83, 0, 129, 0, 0, 0, 89, … (Folge A049283 in OEIS)
Taucht in obiger Liste an der -ten Stelle eine auf, so ist ein Nichttotient, weil es offenbar kein gibt, deren Totient ist.
  • Die nächste Liste gibt die größten an, deren Totient ist (für aufsteigende )
2, 6, 0, 12, 0, 18, 0, 30, 0, 22, 0, 42, 0, 0, 0, 60, 0, 54, 0, 66, 0, 46, 0, 90, 0, 0, 0, 58, 0, 62, 0, 120, 0, 0, 0, 126, 0, 0, 0, 150, 0, 98, 0, 138, 0, 94, 0, 210, 0, 0, 0, 106, 0, 162, 0, 174, 0, 118, 0, 198, 0, 0, 0, 240, 0, 134, 0, 0, 0, 142, 0, 270, 0, 0, 0, 0, 0, 158, 0, 330, 0, … (Folge A057635 in OEIS)
Taucht in obiger Liste an der -ten Stelle eine auf, so ist ein Nichttotient, weil es offenbar kein gibt, deren Totient ist.
  • Die folgende Liste gibt die Anzahl der verschiedenen an, für welche gilt (für aufsteigende ):
2, 3, 0, 4, 0, 4, 0, 5, 0, 2, 0, 6, 0, 0, 0, 6, 0, 4, 0, 5, 0, 2, 0, 10, 0, 0, 0, 2, 0, 2, 0, 7, 0, 0, 0, 8, 0, 0, 0, 9, 0, 4, 0, 3, 0, 2, 0, 11, 0, 0, 0, 2, 0, 2, 0, 3, 0, 2, 0, 9, 0, 0, 0, 8, 0, 2, 0, 0, 0, 2, 0, 17, 0, 0, 0, 0, 0, 2, 0, 10, 0, 2, 0, 6, 0, 0, 0, 6, 0, 0, 0, 3, … (Folge A014197 in OEIS)
Beispiel:
An der -ten Stelle steht die Zahl . Das bedeutet, dass es Lösungen der Gleichung gibt. Somit ist ein Nichttotient.
Es gibt eine Vermutung von Robert Daniel Carmichael aus dem Jahr 1907, welche besagt, dass es entweder keine oder mindestens zwei Lösungen der Gleichung für jedes gibt. Die Vermutung ist also äquivalent dazu, dass in obiger Liste niemals eine 1 auftaucht (siehe Carmichaels Totientenfunktions-Vermutung).
  • Es folgt eine Tabelle, aus der man etwas leichter die Nichttotienten ablesen kann. In der ersten Spalte sind die aufsteigenden , in der zweiten Spalte stehen diejenigen Zahlen, deren Totient 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 als Totient haben, handelt es sich bei um einen Nichttotienten (welcher gelb eingefärbt wird):
  • Sei eine Primzahl. Dann ist niemals ein Nichttotient.
Beweis:
Jede Primzahl ist zu Zahlen teilerfremd (nämlich zu allen natürlichen Zahlen, welche kleiner als sind). Somit ist und ist der Totient von . Also ist kein Nichttotient.
  • Sei eine Primzahl. Dann ist die Rechteckzahl niemals ein Nichttotient.
Beweis:
Wegen den Rechenregeln für die eulersche Phi-Funktion für Primzahlpotenzen erhält man . Somit ist und ist der Totient von . Also ist kein Nichttotient.
  • Alle ungeraden Zahlen außer der Zahl sind Nichttotienten.
  • Für jede natürliche Zahl existiert eine Primzahl , sodass ein Nichttotient ist.[1]
  • Es gibt unendlich viele Primzahlen , sodass alle Zahlen der Form mit Nichttotienten sind (wie zum Beispiel die Sierpinski-Zahlen und ).[2]
  • Jede ungerade Zahl hat ein gerades Vielfaches, welches Nichttotient ist.[3]
  • Es gibt unendlich viele gerade Nichttotienten (folgt aus den vorhergehenden Eigenschaften).

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Mingzhi Zhang: On Nontotients. Theorem 1. Journal of Number Theory 43 (2), Februar 1993, S. 168–172, abgerufen am 26. Februar 2020.
  2. Mingzhi Zhang: On Nontotients. Theorem 5. Journal of Number Theory 43 (2), Februar 1993, S. 168–172, abgerufen am 26. Februar 2020.
  3. Mingzhi Zhang: On Nontotients. Journal of Number Theory 43 (2), Februar 1993, S. 168–172, abgerufen am 26. Februar 2020.