Zum Inhalt springen
Topos Uranos
Deutsch

Primzahlen und der Fundamentalsatz der Arithmetik

Zusammenfassung

Diese Lektion untersucht die Primzahlen, die Atome der Multiplikation der natürlichen Zahlen. Sie beweist, dass jede natürliche Zahl größer als 11 einen Primteiler hat, stellt das Sieb des Eratosthenes vor und den Grund, warum es genügt, bis zur Quadratwurzel zu sieben, und beweist mit Euklid, dass es unendlich viele Primzahlen gibt. Danach beweist sie das Lemma von Euklid, nach dem eine Primzahl, die ein Produkt teilt, einen seiner Faktoren teilt, und mit ihm den Fundamentalsatz der Arithmetik: Jede natürliche Zahl größer als 11 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben. Aus der Primfaktorzerlegung folgen die Anzahl der Teiler einer natürlichen Zahl, die Charakterisierung der Quadratzahlen und die Irrationalität der Quadratwurzel jeder natürlichen Zahl, die keine Quadratzahl ist.

Lernziele

  1. Die Primzahlen von den zusammengesetzten Zahlen unterscheiden und beweisen, dass jede natürliche Zahl größer als 11 einen Primteiler hat.
  2. Das Sieb des Eratosthenes anwenden und begründen, warum es genügt, die Vielfachen der Primzahlen zu streichen, die nicht größer als die Quadratwurzel der Grenze sind.
  3. Die Unendlichkeit der Primzahlen, das Lemma von Euklid sowie die Existenz und die Eindeutigkeit der Primfaktorzerlegung beweisen.
  4. Die Primfaktorzerlegung nutzen, um Teiler zu zählen und aufzulisten, Quadratzahlen zu erkennen und die Irrationalität von Quadratwurzeln zu beweisen.

Primzahlen und zusammengesetzte Zahlen

In der Lektion über Teilbarkeit und Division mit Rest wurde gezeigt, dass jede natürliche Zahl nn durch 11 und durch sich selbst teilbar ist. Manche natürliche Zahlen haben keine anderen Teiler als diese beiden; sie sind die Bausteine, aus denen sich durch Multiplikation alle anderen zusammensetzen.

Definition (Primzahl). Eine natürliche Zahl pp heißt Primzahl, wenn p>1p > 1 gilt und ihre einzigen Teiler 11 und pp sind. Eine natürliche Zahl n>1n > 1, die keine Primzahl ist, heißt zusammengesetzt: Sie lässt sich als n=abn = ab schreiben, mit 1<a<n1 < a < n und 1<b<n1 < b < n. Die Zahl 11 ist weder Primzahl noch zusammengesetzt.

Die Primzahlen kleiner als 5050 sind die folgenden fünfzehn:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,472, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Die Zahl 22 ist die einzige gerade Primzahl, weil jede andere gerade Zahl den Teiler 22 hat, der von 11 und von ihr selbst verschieden ist. Der Ausschluss der 11 ist keine Laune der Definition: Wäre 11 eine Primzahl, so wäre die Primfaktorzerlegung nicht mehr eindeutig, weil 6=2⋅3=1⋅2⋅36 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 gilt, und der zentrale Satz dieser Lektion müsste mit einer Ausnahme formuliert werden.

Das Wohlordnungsprinzip

Die Beweise dieser Lektion stützen sich auf eine Form des Induktionsprinzips, die für Überlegungen über Teiler besonders bequem ist: das Wohlordnungsprinzip, nach dem jede nichtleere Menge natürlicher Zahlen ein kleinstes Element hat. Es wurde in der Lektion über Summen, arithmetische und geometrische Folgen und Induktion aus der starken Induktion hergeleitet und wird hier verwendet, ohne seinen Beweis zu wiederholen.

Jede natürliche Zahl größer als 1 hat einen Primteiler

Das erste Ergebnis der Lektion stellt sicher, dass keine natürliche Zahl größer als 11 den Primzahlen entgeht: Es gibt stets eine, die sie teilt, und man findet sie unter den kleinsten Teilern.

PropositionDer kleinste Teiler größer als 1 ist eine Primzahl

Jede natürliche Zahl n>1n > 1 hat einen Primteiler: Der kleinste Teiler von nn, der größer als 11 ist, ist eine Primzahl. Ist außerdem nn zusammengesetzt, so erfüllt ihr kleinster Primteiler pp die Ungleichung p2≤np^2 \leq n. Die Abbildung markiert auf der Zahlengeraden die Teiler von n=91=7⋅13n = 91 = 7 \cdot 13.

Beweis

  1. D={d∈N:d∣n∧d>1},n∈D,m=min⁡D\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D

    Die Menge der Teiler von nn, die größer als 11 sind, ist nicht leer, weil sie nn selbst enthält; nach dem Wohlordnungsprinzip hat sie ein kleinstes Element mm.

  2. a∣m∧m∣n→a∈D,a<ma \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}

    Wäre mm zusammengesetzt, also m=abm = ab mit 1<a<m1 < a < m, so würde der Faktor aa die Zahl mm teilen und, wegen der Transitivität der Teilbarkeit, auch nn: Er wäre ein Element von DD, das kleiner als mm ist, im Widerspruch zur Wahl von mm. Folglich ist mm eine Primzahl.

  3. n=pk,k∈D\dato{k}{n = pk, \quad k \in D}

    Sei nun nn zusammengesetzt, und sei pp ihr kleinster Primteiler, der das kleinste Element von DD ist. Wir schreiben n=pkn = pk; da nn keine Primzahl ist, gilt k≠1k \neq 1, und auch kk teilt nn.

  4. p2=p⋅p≤p⋅k=np^2 = p \cdot p \leq \resaltar{p \cdot k} = n

    Wegen der Minimalität von pp gilt k≥pk \geq p, und die Monotonie der Multiplikation liefert die Abschätzung.

Um zu entscheiden, ob eine natürliche Zahl nn eine Primzahl ist, genügt es folglich, die Primzahlen pp mit p2≤np^2 \leq n zu prüfen: Teilt keine von ihnen die Zahl, so ist nn eine Primzahl. Zum Beispiel genügt es für 221221, die Primzahlen bis 1313 zu prüfen, denn es gilt 172=289>22117^2 = 289 > 221: Die Zahl ist weder durch 22 noch durch 33, 55, 77 oder 1111 teilbar, wohl aber durch 1313, und es ist 221=13⋅17221 = 13 \cdot 17. Dagegen ist 211211 durch keine der Primzahlen 22, 33, 55, 77, 1111 und 1313 teilbar, und wegen 172=289>21117^2 = 289 > 211 ist die Zahl 211211 eine Primzahl.