______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.4. Primzahlen

_______________________________________________________________________________

Primzahlen sind die multiplikativen Bausteine der ganzen Zahlen, da jede ganze Zahl in Primzahlen faktorisiert werden kann. Diese Faktorisierung ist bei großen Zahlen zumeist sehr aufwendig und es gibt noch kein effizientes Faktorisierungsverfahren. Diese Schwierigkeit wird bei modernen Verschlüsselungsverfahren oft ausgenutzt. Überhaupt haben Primzahlen eine sehr prominente Stellung im Alltag und in der Mathematik.

Eine natürliche Zahl n > 1 heißt Primzahl oder kurz prim, wenn sie nur durch sich selbst und 1 teilbar ist (innerhalb der Menge ℕ); ansonsten nennt man n zusammengesetzt. Die ’ersten’ Primzahlen findet man leicht:

2,3,5,7,11, 13,17,...,30449, ...

Wir starten mit dem Lemma des Euklid, welches wir schon in einem Exkurs zum ersten Kapitel benutzt hatten:

Lemma (Lemma von Euklid).

Teilt eine Primzahl p ein Produkt, so teilt sie mindestens einen der Faktoren:

p | ab ⇒ p | a oder p | b.



Beim Beweis dürfen wir natürlich kein Ergebnis verwenden, welches wir mit Hife des Euklidschen Lemmas bewiesen haben, ansonsten entstünde ein ’Zirkelschluss’ und nichts wäre wirklich bewiesen.

Beweis. Angenommen, p ∤ a, also insbesondere ggT(p,a) = 1 (da p eine Primzahl ist). Nach dem Korollar aus III.1. existieren ganze Zahlen x,y mit

px + ay = 1 bzw. bpx + aby = b.

Wegen p∣pbx und p∣aby folgt p∣b (nach Rechenregel (4) aus dem Kapitel zur Teilbarkeit). qed.

Die Aussage des euklidschen Lemmas ist falsch für zusammengesetzte Zahlen: Beispielsweise teilt 6 das Produkt 2 ⋅ 3, jedoch keinen der Faktoren. Insofern charakterisiert das Lemma von Euklid also Primzahlen! Man überlege sich, wo genau im Beweis davon Gebrauch gemacht wurde, dass p eine Primzahl ist und warum das so entscheidend ist?

Wir haben schon die multiplikative Zerlegbarkeit ganzer Zahlen in Primfaktoren angesprochen. Diese ist sogar eindeutig. So simpel dieser Sachverhalt auch sein mag, diese Beobachtung bildet einen der wichtigsten Sätze der Zahlentheorie überhaupt! Die entsprechende Aussage hätte eigentlich bereits in Euklids Elementen stehen können, jedoch findet man sie erst bei Gauß in seinen berühmten ’Disquisitiones Arithmeticae’ aus dem Jahre 1801.


Satz (Fundamentalsatz der Arithmetik).

Jede natürliche Zahl n besitzt eine eindeutige Primfaktorzerlegung, d.h. es gibt eindeutig bestimmte Exponenten νp(n) ∈ℕ0, so dass

faktorisierung

Hierbei läuft das Produkt über alle Primzahlen; tatsächlich sind stets jedoch nur endlich viele Exponenten νp(n) verschieden von Null. Für n = 1 verschwinden alle Exponenten und das Produkt ist leer.

Beweis. Wir nutzen die Wohlordnung von ℕ. Wir zeigen zunächst die Existenz: Ist n ∈ℕ die kleinste Zahl, für die eine solche Primfaktorzerlegung nicht bekannt ist, so ist n entweder prim oder ein Produkt kleinerer natürlicher Zahlen, für die die Aussage bereits bekannt ist. Also folgt die Existenz einer Primfaktorzerlegung von n.

Nun der Nachweis der Eindeutigkeit: Angenommen, n ist minimal mit zwei wesentlich verschiedenen Primfaktorzerlegungen,

eindeutigkeit

wobei ’wesentlich verschieden’ pi≠qj für alle i,j bedeutet (ansonsten könnten wir ja kürzen). Jedes pi teilt n = q1q2⋅…⋅ qs, also nach dem Lemma von Euklid auch einen Faktor qk. Da pi und qk jeweils prim sind, folgte pi = qk, ein Widerspruch zu unserer Annahme. qed.

Wie reichhaltig ist die Menge der multiplikativen Bausteine der ganzen Zahlen? Eine erste Antwort auf diese Frage gibt ein berühmtes Resultat von Euklid (was heutzutage bereits in der Schule gelehrt wird):

Satz (Euklid).

Es gibt unendlich viele Primzahlen.

Beweis. Wir zeigen: Zu jeder gegebenen endlichen Menge von Primzahlen existiert eine weitere; damit ist die Menge der Primzahlen also nicht endlich! Sei hierzu p1 = 2,p2,…,pm eine Menge von Primzahlen. (Hierbei haben wir p1 explizit mit dem Wert 2 belegt, damit wir nicht mit einer leeren Primzahlmenge argumentieren!) Dann ist die natürliche Zahl

euklid


sicherlich größer als 1 und besitzt also nach dem Fundamentalsatz (mindestens) einen Primfaktor p, d.h. p∣q. (Sie kann dabei auch selbst prim sein, aber das ist hier nicht weiter von Belang!) Käme nun die Primzahl p unter den Primzahlen p1,…,pm vor, so folgte

teiler

Mit q und q − 1 würde dann aber p auch jede Linearkombination dieser beiden Zahlen teilen (4. Rechenregel aus III.1.), also insbesondere

teiler

ein Widerspruch (mittels der 2. Rechenregel aus III.1., denn p ist eine Primzahl, also größer 1). Also war unsere Annahme falsch, d.h. p kommt nicht unter den Primzahlen p1,…,pm vor und der Satz ist bewiesen. qed.

Der Beweis liefert ein Beispiel dafür, zu einer gegebenen Liste von Primzahlen weitere zu finden.
Die Unendlichkeitsaussage von Euklid gibt nur eine unzulängliche Beschreibung für die Primzahlen. Auf den ersten Blick scheinen die Primzahlen wie zufällig aufzutreten, aber gehorcht ihre Verteilung vielleicht doch einer bestimmten erstaunlichen Gesetzmäßigkeit. Ein klassische Fragestellung der Zahlentheorie lautet deshalb:

Wie sind die Primzahlen innerhalb der natürlichen Zahlen verteilt? Veranschaulichen lässt sich diese Frage beispielsweise durch die sogenannte Ulam-Spirale.