Carmichaels Totientenfunktions-Vermutung

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

Für jedes $n$ gibt es mindestens eine positive ganze Zahl $m=n$, sodass gilt:

$\phi (m)=\phi (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).

Man kann die Carmichaelsche Vermutung auch anders formulieren:

Es gibt keine Zahl $m$, die von der Eulerschen Phi-Funktion genau einmal angenommen wird.

Oder als Frage formuliert:

Gibt es eine Zahl $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 $n=6$. Dann gibt es zu dieser Zahl nur die beiden Zahlen $t_1=1$ und $t_2=5$, die zu $n=6$ teilerfremd sind. Somit ist $\phi (6)=2$. Es gibt aber auch zu $n=4$ nur zwei teilerfremde Zahlen, nämlich $t_1=1$ und $t_2=3$. Somit ist auch $\phi (4)=2$ und man hat eine zweite Zahl $m=4=6$ gefunden, deren Totient gleich dem Totienten von $n=6$ ist und es ist $\phi (6)=\phi (4)$. Auch $\phi (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 $n$ welchen Totienten $k$ haben und welche anderen Zahlen $m$ den gleichen Totienten besitzen. Man kann ihr entnehmen, dass die Carmichaelsche Vermutung zumindest bis $k=72$ gilt. Man erkennt auch, dass $\phi (n)$ für $n>2$ stets eine gerade Zahl $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.

$k$	Zahlen $n$, sodass $\phi (n)=k$ ist (Vorlage:OEIS)	Anzahl $A(k)$ dieser $n$ (Vorlage: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 $n$, die die Carmichaelsche Vermutung widerlegen könnten. Carmichael selbst hat im Jahr 1922 bewiesen, dass jedes Gegenbeispiel zu seiner Vermutung (also ein Wert $n$, bei dem sich $\phi (n)$ von den Totienten aller anderen Zahlen unterscheidet) mindestens $10^{37}$ sein muss. Der US-amerikanische Mathematiker Victor Klee erweiterte im Jahr 1947 dieses Ergebnis auf $10^{400}$. Masai und Vallette konnten im Jahr 1982 die untere Grenze für ein Gegenbeispiel auf $10^{10000}$ erhöhen. Die beiden Mathematiker Schlafly und Wagon erhöhten die untere Grenze im Jahr 1994 auf $10^{10000000}$ und letztendlich zeigte der US-amerikanische Mathematiker Kevin Ford im Jahr 1998, dass $10^{10000000000}$ eine untere Grenze sein muss.

Schlafly und Wagon schrieben 1994: Vorlage:Zitat

Eigenschaften, die ein Gegenbeispiel haben muss

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

• $n$ ist eine gerade Zahl.

Beweis:

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

• $n$ ist ein Vielfaches von 4.

Beweis:

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

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

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

• $n$ muss durch die Quadrate der Primteiler von $\phi (n)=k$ teilbar sein.
• $n$ darf nicht durch $8$ teilbar sein.
• $n$ darf nicht durch Fermat-Primzahlen $F_x=3$ (also Primzahlen der Form $F_x=2^{2^x}+1$ mit $x\ne 0$) teilbar sein (es sind, abgesehen von $F_0=3$, nur $F_1=5$, $F_2=17$, $F_3=257$ und $F_4=65537$ bekannt).

Beispiel:

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

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

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

Weitere Ergebnisse

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

• Sei $A(k)=x$ für eine ganze Zahl $k$. Dann existieren unendlich viele solche $k$.

Beispiel:

Dieser von Paul Erdős im Jahr 1958 bewiesene Satz besagt, dass, wenn es ein $k$ gibt mit $A(k)=x$, es unendlich viele solche $k$ gibt. Sei zum Beispiel $A(k):=3$. Dann kann man obiger Tabelle entnehmen, dass für $k\in \{2,44,56,\dots \}$ jeweils exakt 3 verschiedene $m$ existieren, für die jeweils $\phi (m)=k$ gilt. Somit gibt es unendlich viele $k$ mit $A(k)=3$. Das gilt auch für den Fall $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 $x\ge 2$ gibt es eine ganze Zahl $k$, sodass $A(k)=x$ ist.

Beispiel:

Dieser Satz wurde von Wacław Sierpiński in den 1950er-Jahren vermutet und von Kevin Ford im Jahr 1999 bewiesen. Sei $x:=5$. Dann gibt es laut diesem Satz ein $k$, sodass $A(k)=5$ ist. Tatsächlich kann man der obigen Tabelle entnehmen, dass in diesem Fall $k=8$ ist, weil $A(8)=5$ ist. Es kann auch andere $k$ geben, die diese Eigenschaft haben (zum Beispiel $k=20$).

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

Weblinks

• Vorlage:MathWorld
• Vorlage:Internetquelle
• 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.