Warum ist phi 1 gleich 1

Die für mich verblüffendste und faszinierndste Formel der Mathematik ist die auf Leonard Euler zurück zu führende Gleichung eπi +1 = 0. Es handelt sich um einen Spezialfall der Eulerschen Identität. Ihr könnt sie hier in voller Schönheit bewundern:

Das folgende Video versucht die Gleichung e hoch πi + 1 = 0 auf anschaulich Art und Weise zu erklären. Und das ist gar nicht mal so einfach. Denn die komplexen Zahlen und ihre Rechenregeln sind für Nicht-Mathematiker reichlich abstrus und kompliziert 😉

Überhaupt gibt es ziemlich seltsame Zusammenhänge in der komplexen Mathematik. Betrachten wir nur eπ = 23.1406926327792690…, da kämen wir nie auf die Idee, dass so etwas Krummes mit i potenziert so eine simple Zahl als Lösung hat.

Es ist schon schwer genug, sich so etwas wie das Potenzieren mit i vorzustellen. Noch schräger wird es aber, wenn wir i mit sich selber potenzieren. Verblüffenderweise erhalten wir ii = e -π/2 = 0.207879576350… und damit eine reelle Zahl als Ergebnis einer überaus komplexen Rechnung. Voll schräg 😉

Auch die Eulersche φ-Funktion ist geeignet, die Unendlichkeit der Primzahlen zu beweisen. Bei unserer Analyse des Siebverfahrens hatten wir gezeigt:

Satz (Berechnungsformel für die φ-Funktion)

Sei m ≥ 1. Dann gilt

φ(m)  =  m ∏p|m (1 − 1/p)  =  m ∏p|m p − 1p.

Speziell gilt

(+)  φ(m)  =  ∏p|m (p − 1),

falls m ein Produkt von paarweise verschiedenen Primzahlen ist (d. h. m ist quadratfrei). In diesem Fall kürzt sich der Vorfaktor m mit allen Nennern des Produkts auf der rechten Seite des Satzes. Damit können wir leicht zeigen:

Satz (Unendlichkeit der Primzahlen)

Es gibt unendlich viele Primzahlen.

Beweis

Seien p1 < … < pk Primzahlen mit k ≥ 2, und sei m = p1 … pk. Dann gilt

φ(m)  =  (p1 − 1) … (pk − 1)  ≥  pk − 1  ≥  2.

Folglich gibt es neben der 1 eine weitere zu m teilerfremde Zahl n im Intervall { 1, …, m − 1 }. Dann ist aber jeder Primfaktor von n von p1, …, pk verschieden (und wegen n > 1 gibt einen Primfaktor von n). Dies zeigt, dass es unendlich viele Primzahlen gibt.

 Der Beweis zeigt stärker:

Satz (Primzahlen unterhalb einer Primzahlfakultät)

Seien p1 < … < pk die ersten k Primzahlen, wobei k ≥ 2. Dann gibt es eine Primzahl p mit pk < p < pk# = p1 … pk.

 Den Fall k = 1 müssen wir wegen 2 = 2# offenbar ausschließen. Im Fall k = 2 ist zum Beispiel p2# = 3# = 6 und wir finden eine Primzahl zwischen 3 und 6, nämlich die 5.

 Der Beweis von Euklid liefert diese Verstärkung nicht: Bei der „Produkt Plus Eins“-Argumentation kann die betrachtete Zahl Prim sein (etwa 2 · 3 + 1 = 7) und wir erhalten keine Information über die Existenz von Primzahlen unterhalb dieser Zahl (wie der Primzahl 5 zwischen 3 und 7). Die Variante „Produkt Minus Eins“ des Beweises von Euklid ist dagegen geeignet, diese Verstärkung zu beweisen.

 Wir betrachten nun noch einige Varianten des Arguments.

Vermeidung der φ-Funktion

 Das Argument lässt sich auch direkt mit Hilfe der Einschluss-Ausschluss-Darstellung einer Zahl führen. Die φ-Funktion muss dann nicht explizit eingeführt werden:

Satz (Unendlichkeit der Primzahlen)

Es gibt unendlich viele Primzahlen.

Beweis

Annahme, es gibt nur endlich viele Primzahlen. Sei dann m = ∏p prim p das Produkt aller Primzahlen. Dann gilt unter Verwendung des Distributivgesetzes:

Widerspruch.

 In dieser Form erinnert der Beweis an die Argumentation des letzten Essays. Wir verwenden jedoch diesmal kein „Produkt Plus Eins“-Argument.

Vermeidung der Einschluss-Ausschluss-Argumentation

 Bei der folgenden Variante verwenden wir die Definition der φ-Funktion, nicht aber den Berechnungssatz. Wir zeigen elementar:

Satz (gerade φ-Werte)

Sei m ≥ 3. Dann ist φ(m) gerade.

 Die Beweisidee ist sehr einfach: Wir teilen die zu m teilerfremden Zahlen im Intervall { 1, …, m } in zwei gleichgroße Mengen auf. Dies zeigt, dass ihre Anzahl gerade ist. Die Aufteilung wird durch die Eigenschaft

ggT(n, m)  =  (m − n, m)  für alle n = 1, …, m

motiviert, die der Leser vielleicht vom Euklidischen Algorithmus her kennt. Für m = 15 sind genau die Zahlen

1, 2, 4, 7, 8, 11, 13, 14

teilerfremd zu m. Die Paarbildung lautet hier

(1, 14),  (2, 13),  (4, 11),  (7, 8).

Diese Idee übersetzen wir nun in einen formalen Beweis.

Beweis

Wir setzen:

A  =  { 1 ≤ n < m/2 | n und m sind teilerfremd },

B  =  { m/2 < n < m | n und m sind teilerfremd }.

Dann gilt A ∩ B = ∅. Da m ≥ 3 ist, gilt

A  ∪  B  =  { 1 ≤ n ≤ m | n und m sind teilerfremd }.

(Denn es gilt m/2 > 1 und m/2 ist entweder keine natürliche Zahl oder ein Teiler von m.) Damit ist

φ(m)  =  |A| + |B|.

Wir definieren nun eine Funktion f auf A durch

f (n)  =  m − n  für alle n  ∈  A.

Da ggT(n, m) = ggT(m − n, m) für alle n = 1, …, m gilt, ist f : A → B bijektiv. Folglich ist |A| = |B| und damit

φ(m)  =  |A| + |B|  =  2 |A|.

 Damit erhalten wir:

Satz (Unendlichkeit der Primzahlen)

Es gibt unendlich viele Primzahlen.

Beweis

Annahme, es gibt nur endlich viele Primzahlen. Sei dann m = ∏p prim p das Produkt aller Primzahlen. Dann gilt φ(m) = 1, da im Intervall 1, …, m nur die Zahl 1 teilerfremd zu m ist. Offenbar ist aber m ≥ 3, sodass φ(m) gerade und damit größer als 1 ist, Widerspruch.

 Da wir hier nur „φ(m) > 1“ brauchen, lässt sich die Argumentation noch weiter vereinfachen: Es genügt zu wissen, dass φ(m) ≥ 2 für alle m ≥ 3 ist. Dies lässt sich ohne Konstruktion einer Bijektion so einsehen:

(+)  Ist n  ∈  { 1, …, m } teilerfremd zu m, so auch m − n.

Wegen m ≥ 3 ist n ≠ m − n (da sonst 2n = m und damit n = 1 und m = 2 gelten würde). Folglich gibt es mindestens zwei verschiedene zu m teilerfremde Zahlen in { 1, …, m }, sodass φ(m) ≥ 2.

 Die einfachste Wahl von n in (+) ist n = 1. In diesem Fall verwenden wir also, dass m − 1 teilerfremd zu m ist. Damit sind wir letztendlich wieder bei der „Produkt Minus Eins“-Argumentation angekommen, so dass sich unser Beweis nach mehreren Reduzierungen als eine weitere Variante des Beweises von Euklid entpuppt. Er entfaltet aber doch eine andere Wirkung und zeigt, welche Kraft in der Berechnungsformel für die φ-Funktion steckt.

Was berechnet Phi?

Wie berechnet man Phi von n?

Was ist Phi von n?