Carmichaels Totientenfunktions-Vermutung
In der Mathematik ist die Eulersche Phi-Funktion (auch Totient von genannt) eine zahlentheoretische Funktion, die für jede positive natürliche Zahl angibt, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind. Diese Totienten sind oft gleich, so ist zum Beispiel , weil zu den vier Zahlen 1, 2, 3 und 4 teilerfremd und zu den vier Zahlen 1, 3, 7 und 9 teilerfremd ist.
Der US-amerikanische Mathematiker Robert Carmichael stellte die folgende Behauptung im Jahr 1907 als Übungsaufgabe auf:[1]
- Für jedes gibt es mindestens eine positive ganze Zahl , sodass gilt:
Carmichael war der Meinung, er hätte diese Behauptung bewiesen, und hat diese Behauptung 1907 als einen mathematischen Satz formuliert und sogar 1914 als Übungsaufgabe in sein Lehrbuch Theory of numbers (Kapitel 2) aufgenommen. Allerdings war sein Beweis fehlerhaft. Er zog im Jahr 1922 seine Behauptung zurück, nachdem mehrere Personen ihn auf eine Lücke im Beweis hingewiesen hatten, und erklärte die Vermutung als offenes Problem, die man nun Carmichaels Totientenfunktions-Vermutung oder kurz Carmichaels Vermutung bzw. Carmichaelsche Vermutung nennt (englisch Carmichael’s totient function conjecture).[2][3]
Man kann die Carmichaelsche Vermutung auch anders formulieren:
- Es gibt keine Zahl , die von der Eulerschen Phi-Funktion genau einmal angenommen wird.
Oder als Frage formuliert:
- Gibt es eine Zahl , die von der Eulerschen Phi-Funktion genau einmal angenommen wird?
Wenn die Carmichaelsche Vermutung stimmt, müsste man diese Frage mit „Nein!“ beantworten.
Beispiele
Bearbeiten- Sei . Dann gibt es zu dieser Zahl nur die beiden Zahlen und , die zu teilerfremd sind. Somit ist . Es gibt aber auch zu nur zwei teilerfremde Zahlen, nämlich und . Somit ist auch und man hat eine zweite Zahl gefunden, deren Totient gleich dem Totienten von ist und es ist . Auch (weil 3 zu 1 und 2 teilerfremd ist). Es gibt somit sogar drei Zahlen, deren Totient gleich 2 ist.
- Die folgende Tabelle gibt an, welche Zahlen welchen Totienten haben und welche anderen Zahlen den gleichen Totienten besitzen. Man kann ihr entnehmen, dass die Carmichaelsche Vermutung zumindest bis gilt. Man erkennt auch, dass für stets eine gerade Zahl ist (siehe Eigenschaften der Eulerschen Phi-Funktion). Würde die Carmichaelsche Vermutung nicht stimmen, müsste irgendwann in der dritten Spalte eine 1 auftauchen.
Zahlen , sodass ist (Folge A032447 in OEIS) | Anzahl dieser (Folge A014197 in OEIS) | |
---|---|---|
1 | 1, 2 | 2 |
2 | 3, 4, 6 | 3 |
4 | 5, 8, 10, 12 | 4 |
6 | 7, 9, 14, 18 | 4 |
8 | 15, 16, 20, 24, 30 | 5 |
10 | 11, 22 | 2 |
12 | 13, 21, 26, 28, 36, 42 | 6 |
16 | 17, 32, 34, 40, 48, 60 | 6 |
18 | 19, 27, 38, 54 | 4 |
20 | 25, 33, 44, 50, 66 | 5 |
22 | 23, 46 | 2 |
24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 10 |
28 | 29, 58 | 2 |
30 | 31, 62 | 2 |
32 | 51, 64, 68, 80, 96, 102, 120 | 7 |
36 | 37, 57, 63, 74, 76, 108, 114, 126 | 8 |
40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 9 |
42 | 43, 49, 86, 98 | 4 |
44 | 69, 92, 138 | 3 |
46 | 47, 94 | 2 |
48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 11 |
52 | 53, 106 | 2 |
54 | 81, 162 | 2 |
56 | 87, 116, 174 | 3 |
58 | 59, 118 | 2 |
60 | 61, 77, 93, 99, 122, 124, 154, 186, 198 | 9 |
64 | 85, 128, 136, 160, 170, 192, 204, 240 | 8 |
66 | 67, 134 | 2 |
70 | 71, 142 | 2 |
72 | 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 | 17 |
Untere Grenzen
BearbeitenEs gibt sehr hohe untere Grenzen für , die die Carmichaelsche Vermutung widerlegen könnten. Carmichael selbst hat im Jahr 1922 bewiesen, dass jedes Gegenbeispiel zu seiner Vermutung (also ein Wert , bei dem sich von den Totienten aller anderen Zahlen unterscheidet) mindestens sein muss.[2] Der US-amerikanische Mathematiker Victor Klee erweiterte im Jahr 1947 dieses Ergebnis auf .[4] Masai und Vallette konnten im Jahr 1982 die untere Grenze für ein Gegenbeispiel auf erhöhen.[5] Die beiden Mathematiker Schlafly und Wagon erhöhten die untere Grenze im Jahr 1994 auf [6] und letztendlich zeigte der US-amerikanische Mathematiker Kevin Ford im Jahr 1998,[7] dass eine untere Grenze sein muss.[8][9]
Schlafly und Wagon schrieben 1994:[6][10]
“We do not know of another unsolved problem in mathematics for which a lower bound on a counterexample is so high. (…) There can be little doubt that Carmichael’s conjecture is true.”
„Wir kennen kein anderes ungelöstes Problem in der Mathematik, bei dem die untere Schranke für ein Gegenbeispiel so hoch ist. (…) Es kann wenig Zweifel geben, dass Carmichaels Vermutung wahr ist.“
Eigenschaften, die ein Gegenbeispiel haben muss
BearbeitenSei ein Gegenbeispiel von Carmichaels Totientenfunktions-Vermutung mit (es muss also für alle gelten: ). Dann muss gelten:
- ist eine gerade Zahl.[2]
- Beweis:
- Wäre ungerade, so würde gelten (siehe Eigenschaften der Eulerschen Phi-Funktion) und man hätte erst recht zwei Zahlen mit gleichem Totienten. Somit muss eine gerade Zahl sein.
- Beweis:
- ist ein Vielfaches von 4.[2]
- Beweis:
- Wäre kein Vielfaches von 4, so muss wegen obiger Aussage eine gerade Zahl sein. Somit ist und man hätte erst recht zwei Zahlen mit gleichem Totienten. Somit muss ein Vielfaches von 4 sein.
- Beweis:
- Sei und teilbar durch eine Primzahl der Form . Dann gilt:[2]
- ist teilbar durch das Quadrat dieser Primzahl (also durch ).
- muss durch die Quadrate der Primteiler von teilbar sein.[4]
- darf nicht durch teilbar sein.[4]
- darf nicht durch Fermat-Primzahlen (also Primzahlen der Form mit ) teilbar sein (es sind, abgesehen von , nur , , und bekannt).[4]
- Beispiel:
- Will man kontrollieren, ob ein Gegenbeispiel von Carmichaels Totientenfunktions-Vermutung ist, so muss man die Primfaktorzerlegung von betrachten. Die Quadrate der Primteiler von sind und , und muss durch und teilbar sein. Leider ist aber nicht durch teilbar, somit kommt nicht als Gegenbeispiel in Frage. Wäre auch durch teilbar, wäre sie ein Kandidat für ein Gegenbeispiel, weil sie weder durch , , , oder teilbar ist. Aber selbst dann wäre es sehr unwahrscheinlich, dass tatsächlich ein Gegenbeispiel ist. ist eben nur ein Kandidat für ein Gegenbeispiel.
- Beispiel:
- Sei eine Primzahl, sodass ein Teiler von ist. Dann gilt:[11]
- teilt .
- Pomerance zeigte im Jahr 1974, dass die Existenz einer solchen ganzen Zahl höchst unwahrscheinlich ist. Wenn eine solche Zahl existiert, dann gibt es allerdings unendlich viele Gegenbeispiele zu Carmichaels Totientenfunktions-Vermutung. Wenn es keine solchen Zahlen gibt, bedeutet es aber noch immer nicht, dass Carmichaels Vermutung stimmt ( könnte ganz andere Teiler haben).
Aus den angeführten Sätzen wird klar, dass ein Gegenbeispiel zur Vermutung sehr viele Primteiler haben muss. Eine Strategie zum Beweis der Vermutung besteht darin, zu zeigen, dass das Gegenbeispiel unendlich viele Primteiler haben muss. Sei die Menge dieser Primteiler eines Gegenbeispiels. Ford zeigte 2014,[12] dass die Menge sehr „dünn“ ist: Sei die Anzahl der Elemente aus , die kleiner gleich sind, dann ist nach Ford für eine Konstante mit dem Landau-Symbol . Das macht einen Beweis über diese Strategie sehr schwierig.
Weitere Ergebnisse
BearbeitenSei die Anzahl der verschiedenen , für die gilt (wie in der dritten Spalte der obigen Tabelle). Dann gelten folgende Sätze:[10]
- Sei für eine ganze Zahl . Dann existieren unendlich viele solche .[13]
- Beispiel:
- Dieser von Paul Erdős im Jahr 1958 bewiesene Satz besagt, dass, wenn es ein gibt mit , es unendlich viele solche gibt. Sei zum Beispiel . Dann kann man obiger Tabelle entnehmen, dass für jeweils exakt 3 verschiedene existieren, für die jeweils gilt. Somit gibt es unendlich viele mit . Das gilt auch für den Fall , also den Fall eines Gegenbeispiels zu Carmichaels Vermutung. Gibt es also ein Gegenbeispiel zur Vermutung, so gibt es unendlich viele weitere Gegenbeispiele.
- Beispiel:
- Für jede ganze Zahl gibt es eine ganze Zahl , sodass ist.[8]
- Beispiel:
- Dieser Satz wurde von Wacław Sierpiński in den 1950er-Jahren vermutet und von Kevin Ford im Jahr 1999 bewiesen. Sei . Dann gibt es laut diesem Satz ein , sodass ist. Tatsächlich kann man der obigen Tabelle entnehmen, dass in diesem Fall ist, weil ist. Es kann auch andere geben, die diese Eigenschaft haben (zum Beispiel ).
- Beispiel:
Auch diese beiden Sätze machen die Existenz eines Gegenbeispiels zu Carmichaels Vermutung sehr unwahrscheinlich.
Weblinks
Bearbeiten- Eric W. Weisstein: Carmichael’s Totient Function Conjecture. In: MathWorld (englisch).
- Florentin Smarandache: On Carmichaël’s conjecture. University of New Mexico, 1986, S. 1–4, abgerufen am 23. April 2022.
- Sophia D. Merow: Has Carmichael’s totient conjecture been proven? No no, it has not. Notices AMS, Mai 2019, S. 759–761 (Kolumne Math outside the bubble), online.
Einzelnachweise
Bearbeiten- ↑ Robert Daniel Carmichael: On Euler’s -function. Bulletin of the American Mathematical Society 13 (5), 1907, S. 241–243, abgerufen am 17. April 2022.
- ↑ a b c d e Robert Daniel Carmichael: Note on Euler’s -function. Bulletin of the American Mathematical Society 28 (3), 1922, S. 109–110, abgerufen am 17. April 2022.
- ↑ Carmichaelsche Vermutung. Spektrum.de, abgerufen am 16. April 2022.
- ↑ a b c d Victor LaRue Klee: On a conjecture of Carmichael. Bulletin of the American Mathematical Society 53 (12), 1947, S. 1183–1186, abgerufen am 23. April 2022.
- ↑ Pierre Masai, Alain Valette: A lower bound for a counterexample to Carmichael’s conjecture. Boll. Un. Mat. Ital. 1 (6), 1982, S. 313–316, abgerufen am 23. April 2022.
- ↑ a b Aaron Schlafly, Stan Wagon: Carmichael’s conjecture on the Euler function is valid below 1010,000,000. Mathematics of Computation 63 (207), 1994, S. 415–419, abgerufen am 17. April 2022.
- ↑ Kevin Ford: The distribution of totients. Ramanujan Journal, Nr. 1–2, 1998, S. 67–151.
- ↑ a b Kevin Ford: The number of solutions of . Annals of Mathematics 150 (1), 1999, S. 283–311, abgerufen am 17. April 2022.
- ↑ Jozsef Sándor, Borislav Crstici: Handbook of number theory II. Kluwer Academic Publishers, 2004, S. 228–229, abgerufen am 17. April 2022.
- ↑ a b Brian D. Beasley: The Resolved and Unresolved Conjectures of R. D. Carmichael. ACMS 21st Biennial Conference Proceedings, Charleston Southern University, S. 2–3, abgerufen am 23. April 2022.
- ↑ Carl Pomerance: On Carmichael’s conjecture. Proceedings of the American Mathematical Society 43 (2), 1974, S. 297–298, abgerufen am 23. April 2022.
- ↑ Kevin Ford: Sieving very thin sets of primes, and Pratt trees with missing primes. Int. Math. Res. Not. IMRN, Nr. 11, 2014, S. 2955–2971.
- ↑ Paul Erdős: Some remarks on Euler’s -function. Acta Arithmetica 4, 1958, S. 10–19, abgerufen am 23. April 2022.