Carmichaels Totientenfunktions-Vermutung

In der Mathematik ist die Eulersche Phi-Funktion ${\displaystyle \varphi (n)}$ (auch Totient von ${\displaystyle n}$ genannt) eine zahlentheoretische Funktion, die für jede positive natürliche Zahl ${\displaystyle n}$ angibt, wie viele zu ${\displaystyle n}$ teilerfremde natürliche Zahlen es gibt, die nicht größer als ${\displaystyle n}$ sind. Diese Totienten sind oft gleich, so ist zum Beispiel ${\displaystyle \varphi (5)=\varphi (10)=4}$, weil ${\displaystyle n=5}$ zu den vier Zahlen 1, 2, 3 und 4 teilerfremd und ${\displaystyle n=10}$ 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 ${\displaystyle n}$ gibt es mindestens eine positive ganze Zahl ${\displaystyle m\not =n}$, sodass gilt:

${\displaystyle \varphi (m)=\varphi (n)}$

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 ${\displaystyle m}$, die von der Eulerschen Phi-Funktion genau einmal angenommen wird.

Oder als Frage formuliert:

Gibt es eine Zahl ${\displaystyle m}$, die von der Eulerschen Phi-Funktion genau einmal angenommen wird?

Wenn die Carmichaelsche Vermutung stimmt, müsste man diese Frage mit „Nein!“ beantworten.

Beispiele

• Sei ${\displaystyle n=6}$. Dann gibt es zu dieser Zahl nur die beiden Zahlen ${\displaystyle t_{1}=1}$ und ${\displaystyle t_{2}=5}$, die zu ${\displaystyle n=6}$ teilerfremd sind. Somit ist ${\displaystyle \varphi (6)=2}$. Es gibt aber auch zu ${\displaystyle n=4}$ nur zwei teilerfremde Zahlen, nämlich ${\displaystyle t_{1}=1}$ und ${\displaystyle t_{2}=3}$. Somit ist auch ${\displaystyle \varphi (4)=2}$ und man hat eine zweite Zahl ${\displaystyle m=4\not =6}$ gefunden, deren Totient gleich dem Totienten von ${\displaystyle n=6}$ ist und es ist ${\displaystyle \varphi (6)=\varphi (4)}$. Auch ${\displaystyle \varphi (3)=2}$ (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 ${\displaystyle n}$ welchen Totienten ${\displaystyle k}$ haben und welche anderen Zahlen ${\displaystyle m}$ den gleichen Totienten besitzen. Man kann ihr entnehmen, dass die Carmichaelsche Vermutung zumindest bis ${\displaystyle k=72}$ gilt. Man erkennt auch, dass ${\displaystyle \varphi (n)}$ für ${\displaystyle n>2}$ stets eine gerade Zahl ${\displaystyle k}$ ist (siehe Eigenschaften der Eulerschen Phi-Funktion). Würde die Carmichaelsche Vermutung nicht stimmen, müsste irgendwann in der dritten Spalte eine 1 auftauchen.

${\displaystyle k}$	Zahlen ${\displaystyle n}$, sodass ${\displaystyle \varphi (n)=k}$ ist (Folge A032447 in OEIS)	Anzahl ${\displaystyle A(k)}$ dieser ${\displaystyle n}$ (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

Es gibt sehr hohe untere Grenzen für ${\displaystyle n}$, die die Carmichaelsche Vermutung widerlegen könnten. Carmichael selbst hat im Jahr 1922 bewiesen, dass jedes Gegenbeispiel zu seiner Vermutung (also ein Wert ${\displaystyle n}$, bei dem sich ${\displaystyle \varphi (n)}$ von den Totienten aller anderen Zahlen unterscheidet) mindestens ${\displaystyle 10^{37}}$ sein muss.[2] Der US-amerikanische Mathematiker Victor Klee erweiterte im Jahr 1947 dieses Ergebnis auf ${\displaystyle 10^{400}}$.[4] Masai und Vallette konnten im Jahr 1982 die untere Grenze für ein Gegenbeispiel auf ${\displaystyle 10^{10\,000}}$ erhöhen.[5] Die beiden Mathematiker Schlafly und Wagon erhöhten die untere Grenze im Jahr 1994 auf ${\displaystyle 10^{10\,000\,000}}$[6] und letztendlich zeigte der US-amerikanische Mathematiker Kevin Ford im Jahr 1998,[7] dass ${\displaystyle 10^{10\,000\,000\,000}}$ 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.“

– Aaron Schlafly, Stan Wagon

Eigenschaften, die ein Gegenbeispiel haben muss

Sei ${\displaystyle n}$ ein Gegenbeispiel von Carmichaels Totientenfunktions-Vermutung mit ${\displaystyle \varphi (n)=k}$ (es muss also für alle ${\displaystyle m\not =n}$ gelten: ${\displaystyle \varphi (m)\not =\varphi (n)}$). Dann muss gelten:

• ${\displaystyle n}$ ist eine gerade Zahl.[2]

Beweis:

Wäre ${\displaystyle n}$ ungerade, so würde ${\displaystyle \varphi (n)=1\cdot \varphi (n)=\varphi (2)\cdot \varphi (n)=\varphi (2n)}$ gelten (siehe Eigenschaften der Eulerschen Phi-Funktion) und man hätte erst recht zwei Zahlen mit gleichem Totienten. Somit muss ${\displaystyle n}$ eine gerade Zahl sein. ${\displaystyle \Box }$

• ${\displaystyle n}$ ist ein Vielfaches von 4.[2]

Beweis:

Wäre ${\displaystyle n}$ kein Vielfaches von 4, so muss ${\displaystyle n}$ wegen obiger Aussage eine gerade Zahl sein. Somit ist ${\displaystyle \varphi ({\frac {n}{2}})=1\cdot \varphi ({\frac {n}{2}})=\varphi (2)\cdot \varphi ({\frac {n}{2}})=\varphi (n)}$ und man hätte erst recht zwei Zahlen mit gleichem Totienten. Somit muss ${\displaystyle n}$ ein Vielfaches von 4 sein. ${\displaystyle \Box }$

• Sei ${\displaystyle n:=4s}$ und ${\displaystyle s}$ teilbar durch eine Primzahl der Form ${\displaystyle p=2^{x}+1}$. Dann gilt:[2]

${\displaystyle s}$ ist teilbar durch das Quadrat dieser Primzahl (also durch ${\displaystyle p^{2}}$).

• ${\displaystyle n}$ muss durch die Quadrate der Primteiler von ${\displaystyle \varphi (n)=k}$ teilbar sein.[4]
• ${\displaystyle n}$ darf nicht durch ${\displaystyle 8}$ teilbar sein.[4]
• ${\displaystyle n}$ darf nicht durch Fermat-Primzahlen ${\displaystyle F_{x}\not =3}$ (also Primzahlen der Form ${\displaystyle F_{x}=2^{\;\!2^{x}}+1}$ mit ${\displaystyle x\neq 0}$) teilbar sein (es sind, abgesehen von ${\displaystyle F_{0}=3}$, nur ${\displaystyle F_{1}=5}$, ${\displaystyle F_{2}=17}$, ${\displaystyle F_{3}=257}$ und ${\displaystyle F_{4}=65537}$ bekannt).[4]

Beispiel:

Will man kontrollieren, ob ${\displaystyle n=270}$ ein Gegenbeispiel von Carmichaels Totientenfunktions-Vermutung ist, so muss man die Primfaktorzerlegung von ${\displaystyle \varphi (270)=72=2^{3}\cdot 3^{2}}$ betrachten. Die Quadrate der Primteiler von ${\displaystyle k=72}$ sind ${\displaystyle 2^{2}=4}$ und ${\displaystyle 3^{2}=9}$, und ${\displaystyle n=270}$ muss durch ${\displaystyle 4}$ und ${\displaystyle 9}$ teilbar sein. Leider ist aber ${\displaystyle n=270}$ nicht durch ${\displaystyle 4}$ teilbar, somit kommt ${\displaystyle n=270}$ nicht als Gegenbeispiel in Frage. Wäre ${\displaystyle n=270}$ auch durch ${\displaystyle 4}$ teilbar, wäre sie ein Kandidat für ein Gegenbeispiel, weil sie weder durch ${\displaystyle 8}$, ${\displaystyle 5}$, ${\displaystyle 17}$, ${\displaystyle 257}$ oder ${\displaystyle 65537}$ teilbar ist. Aber selbst dann wäre es sehr unwahrscheinlich, dass ${\displaystyle n}$ tatsächlich ein Gegenbeispiel ist. ${\displaystyle n}$ ist eben nur ein Kandidat für ein Gegenbeispiel.

• Sei ${\displaystyle p\in \mathbb {P} }$ eine Primzahl, sodass ${\displaystyle p-1}$ ein Teiler von ${\displaystyle \varphi (n)}$ ist. Dann gilt:[11]

${\displaystyle p^{2}}$ teilt ${\displaystyle n}$.

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 (${\displaystyle n}$ 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 ${\displaystyle S}$ die Menge dieser Primteiler eines Gegenbeispiels. Ford zeigte 2014,[12] dass die Menge ${\displaystyle S}$ sehr „dünn“ ist: Sei ${\displaystyle P(x)}$ die Anzahl der Elemente aus ${\displaystyle S}$, die kleiner gleich ${\displaystyle x}$ sind, dann ist nach Ford ${\displaystyle P(x)=O(x^{1-c})}$ für eine Konstante ${\displaystyle c>0}$ mit dem Landau-Symbol ${\displaystyle O}$. Das macht einen Beweis über diese Strategie sehr schwierig.

Weitere Ergebnisse

Sei ${\displaystyle A(k)}$ die Anzahl der verschiedenen ${\displaystyle m}$, für die ${\displaystyle \varphi (m)=k}$ gilt (wie in der dritten Spalte der obigen Tabelle). Dann gelten folgende Sätze:[10]

• Sei ${\displaystyle A(k)=x}$ für eine ganze Zahl ${\displaystyle k}$. Dann existieren unendlich viele solche ${\displaystyle k}$.[13]

Beispiel:

Dieser von Paul Erdős im Jahr 1958 bewiesene Satz besagt, dass, wenn es ein ${\displaystyle k}$ gibt mit ${\displaystyle A(k)=x}$, es unendlich viele solche ${\displaystyle k}$ gibt. Sei zum Beispiel ${\displaystyle A(k):=3}$. Dann kann man obiger Tabelle entnehmen, dass für ${\displaystyle k\in \{2,44,56,\ldots \}}$ jeweils exakt 3 verschiedene ${\displaystyle m}$ existieren, für die jeweils ${\displaystyle \varphi (m)=k}$ gilt. Somit gibt es unendlich viele ${\displaystyle k}$ mit ${\displaystyle A(k)=3}$. Das gilt auch für den Fall ${\displaystyle A(k)=1}$, also den Fall eines Gegenbeispiels zu Carmichaels Vermutung. Gibt es also ein Gegenbeispiel zur Vermutung, so gibt es unendlich viele weitere Gegenbeispiele.

• Für jede ganze Zahl ${\displaystyle x\geq 2}$ gibt es eine ganze Zahl ${\displaystyle k}$, sodass ${\displaystyle A(k)=x}$ 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 ${\displaystyle x:=5}$. Dann gibt es laut diesem Satz ein ${\displaystyle k}$, sodass ${\displaystyle A(k)=5}$ ist. Tatsächlich kann man der obigen Tabelle entnehmen, dass in diesem Fall ${\displaystyle k=8}$ ist, weil ${\displaystyle A(8)=5}$ ist. Es kann auch andere ${\displaystyle k}$ geben, die diese Eigenschaft haben (zum Beispiel ${\displaystyle k=20}$).

Auch diese beiden Sätze machen die Existenz eines Gegenbeispiels zu Carmichaels Vermutung sehr unwahrscheinlich.

Weblinks

• 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

1. Robert Daniel Carmichael: On Euler’s ${\displaystyle \phi }$-function. Bulletin of the American Mathematical Society 13 (5), 1907, S. 241–243, abgerufen am 17. April 2022. 
2. Robert Daniel Carmichael: Note on Euler’s ${\displaystyle \varphi }$-function. Bulletin of the American Mathematical Society 28 (3), 1922, S. 109–110, abgerufen am 17. April 2022. 
3. Carmichaelsche Vermutung. Spektrum.de, abgerufen am 16. April 2022. 
4. 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. 
5. 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. 
6. Aaron Schlafly, Stan Wagon: Carmichael’s conjecture on the Euler function is valid below 10^10,000,000. Mathematics of Computation 63 (207), 1994, S. 415–419, abgerufen am 17. April 2022. 
7. Kevin Ford: The distribution of totients. Ramanujan Journal, Nr. 1–2, 1998, S. 67–151.
8. Kevin Ford: The number of solutions of ${\displaystyle \varphi (x)=m}$. Annals of Mathematics 150 (1), 1999, S. 283–311, abgerufen am 17. April 2022. 
9. Jozsef Sándor, Borislav Crstici: Handbook of number theory II. Kluwer Academic Publishers, 2004, S. 228–229, abgerufen am 17. April 2022. 
10. 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. 
11. Carl Pomerance: On Carmichael’s conjecture. Proceedings of the American Mathematical Society 43 (2), 1974, S. 297–298, abgerufen am 23. April 2022. 
12. 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.
13. Paul Erdős: Some remarks on Euler’s ${\displaystyle \phi }$-function. Acta Arithmetica 4, 1958, S. 10–19, abgerufen am 23. April 2022.