Fundamentalsatz der Arithmetik
Dieser Satz besagt, dass jede ganze Zahl größer als 1 entweder eine Primzahl ist oder eindeutig als Produkt von Primzahlen dargestellt werden kann, wobei die Reihenfolge der Faktoren keine Rolle spielt. Zum Beispiel: [latex]1200 = 2^4 times 3^1 times 5^2[/latex]. Faktorisierung ist ein Eckpfeiler der Zahlentheorie und liefert eine grundlegende multiplikative Struktur für die ganzen Zahlen.
Der Fundamentalsatz der Arithmetik, auch Satz über die eindeutige Primfaktorzerlegung genannt, besteht aus zwei Hauptaussagen für jede ganze Zahl n > 1: Erstens, dass n als Produkt von Primzahlen geschrieben werden kann (Existenzaussage), und zweitens, dass dieses Produkt, abgesehen von der Reihenfolge der Faktoren, eindeutig ist (Eindeutigkeitsaussage). Die Existenz einer Primfaktorzerlegung wird üblicherweise mittels vollständiger Induktion bewiesen. Der Induktionsanfang ist, dass 2 eine Primzahl ist. Im Induktionsschritt wird angenommen, dass jede ganze Zahl bis k eine Primfaktorzerlegung besitzt. Für k + 1 ist die Primfaktorzerlegung entweder prim (und der Beweis ist abgeschlossen) oder zusammengesetzt. Im letzteren Fall kann sie als Produkt zweier kleinerer ganzer Zahlen, a × b, geschrieben werden. Nach der Induktionsvoraussetzung besitzen sowohl [latex]a[/latex] als auch [latex]b[/latex] Primfaktorzerlegungen, und ihr Produkt ergibt eine Primfaktorzerlegung für [latex]k+1[/latex].
Der Eindeutigkeitsaspekt ist subtiler und beruht entscheidend auf dem Lemma von Euklid. Dieses besagt, dass, wenn eine Primzahl p ein Produkt ab teilt, p entweder a oder b teilen muss. Um die Eindeutigkeit zu beweisen, nehmen wir an, dass eine ganze Zahl n zwei verschiedene Primfaktorzerlegungen besitzt: n = p₁ p₂ ⋅ pₖ = q₁ q₂ ⋅ qₘ. Die Primzahl p₁ teilt die linke Seite, also muss sie auch die rechte Seite teilen. Nach dem Lemma von Euklid muss p₁ eines der qⱼ teilen. Da alle j Primzahlen q_j sind, muss p_1 gleich einer j Primzahl q_j sein. Wir können diese Terme dann auf beiden Seiten kürzen und den Vorgang wiederholen, wodurch wir schließlich zeigen, dass die beiden Faktorisierungen identisch sein müssen. Obwohl Elemente dieses Satzes bereits in Euklids *Elementen* (um 300 v. Chr.) auftauchten, lieferte Carl Friedrich Gauß in seinem Werk *Disquisitiones Arithmeticae* von 1801 die erste klare Formulierung und einen strengen Beweis und festigte damit seine grundlegende Rolle in der Zahlentheorie.
UNESCO Nomenclature: 1101
– Reine Mathematik
Verwendung
Weitverbreitete Verwendung
Vorläufer
- Euklids Beweis der Unendlichkeit der Primzahlen
- Euklidsches Lemma
- Das Konzept der Primzahlen und der Teilbarkeit aus der antiken griechischen Mathematik
- Entwicklung der mathematischen Induktion als Beweistechnik
Anwendungen
- Kryptographie (zB RSA-Algorithmus)
- Algorithmen zum Finden des größten gemeinsamen Teilers (GGT)
- Lösen diophantischer Gleichungen
- Entwicklung der abstrakten Algebra
- Informatikalgorithmen zur Ganzzahlfaktorisierung
Potenzielle Innovationsideen
Aufgrund des hohen Datenverkehrs durch Web-Scraping-Bots, der derzeit mehr als 40.000 Anfragen pro Tag umfasst, ist dieser Inhalt ausschließlich Community-Mitgliedern vorbehalten.
> Anmelden < oder > Registrieren < (100% kostenlos) Zugriff darauf sowie auf alle anderen eingeschränkten Inhalte und Tools.
Related to: fundamental theorem of arithmetic, prime factorization, unique factorization, number theory, integer, prime number, Euclid, Gauss, canonical representation, multiplicative structure.