Teilbarkeit und Primzahlen

Teilbarkeit, der größte gemeinsame Teiler und die Primzahlen bilden das Fundament der Zahlentheorie: Jede ganze Zahl wird multiplikativ aus Primzahlen aufgebaut, und die Art und Weise dieses Aufbaus bestimmt nahezu jedes spätere Ergebnis.

Definition

Eine ganze Zahl a teilt b, wenn b gleich a mal einer ganzen Zahl ist; eine Primzahl ist eine ganze Zahl größer als eins, deren einzige positive Teiler eins und sie selbst sind. Teilbarkeit und Primzahlen betreffen die multiplikative Zerlegung ganzer Zahlen und die irreduziblen Bausteine dieser Zerlegung.

Scope

Dieses Thema behandelt die Teilbarkeitsrelation bei ganzen Zahlen, den Divisionsalgorithmus, größte gemeinsame Teiler und kleinste gemeinsame Vielfache, die mittels des euklidischen Algorithmus berechnet werden, die Bézout-Identität, das Lemma von Euklid, den Fundamentalsatz der Arithmetik und die elementare Theorie der Primzahlen – ihre Unendlichkeit, Verteilungsheuristiken und Primalität.

Core questions

• Wie berechnet der euklidische Algorithmus größte gemeinsame Teiler und liefert die Bézout-Identität?
• Warum erzwingt das Lemma von Euklid, dass die Faktorisierung in Primzahlen eindeutig ist?
• Wie kann man beweisen, dass es unendlich viele Primzahlen gibt, und was offenbaren solche Beweise?
• Wie sind Primzahlen unter den ganzen Zahlen verteilt, und wie wird Primalität in der Praxis entschieden?

Key theories

Divisionsalgorithmus und der euklidische Algorithmus

Jede ganze Zahl, die durch eine positive ganze Zahl geteilt wird, hinterlässt einen eindeutigen Quotienten und Rest; die Iteration dieses Vorgangs ergibt den größten gemeinsamen Teiler und, durch Rücksubstitution, ganze Zahlen, die ihn als Linearkombination ausdrücken (Bézout-Identität).

Fundamentalsatz der Arithmetik

Jede ganze Zahl größer als eins ist ein Produkt von Primzahlen, das bis auf die Reihenfolge eindeutig ist; das Lemma von Euklid (eine Primzahl, die ein Produkt teilt, teilt einen Faktor) ist der entscheidende Schritt.

Unendlichkeit der Primzahlen

Euklids klassisches Argument zeigt, dass keine endliche Liste von Primzahlen vollständig ist; Eulers Produktformel für die Zeta-Funktion liefert einen analytischen Beweis und quantifiziert die Primzahldichte durch die Divergenz der Summe der Kehrwerte der Primzahlen.

Clinical relevance

Schnelle Faktorisierung und Primalitätstests sind grundlegend für die Kryptographie: Die Sicherheit von RSA beruht auf der Schwierigkeit, große Produkte zweier Primzahlen zu faktorisieren, während effiziente Primalitätstests (wie Miller-Rabin) die Schlüsselgenerierung praktikabel machen.

History

Euklids Elemente (ca. 300 v. Chr.) enthielten bereits den euklidischen Algorithmus, das Lemma von Euklid und den Beweis, dass Primzahlen unendlich sind. Das Sieb des Eratosthenes lieferte die erste systematische Methode zur Auflistung von Primzahlen, und die Arbeiten von Euler, Legendre und Gauß im achtzehnten und neunzehnten Jahrhundert formulierten die Primzahlverteilung als quantitatives Problem neu.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

Ist eins eine Primzahl?

Nein. Eins ist per Definition ausgeschlossen, damit die Primfaktorzerlegung eindeutig ist; würde eins als Primzahl zählen, hätte jede Zahl unendlich viele Faktorisierungen.

Wofür wird die Bézout-Identität verwendet?

Sie besagt, dass der größte gemeinsame Teiler zweier ganzer Zahlen eine ganzzahlige Linearkombination von ihnen ist, was die Grundlage für die Berechnung modularer Inversen und die Lösung linearer diophantischer Gleichungen bildet.