Grundsatz der Arithmetik - Fundamental theorem of arithmetic

Der einzigartige Faktorisierungssatz wurde von Gauß mit seinem 1801 erschienenen Buch Disquisitiones Arithmeticae bewiesen . In diesem Buch verwendet Gauß den fundamentalen Satz zum Beweis des Gesetzes der quadratischen Reziprozität .

In der Zahlentheorie besagt der fundamentale Satz der Arithmetik , der auch als eindeutiger Faktorisierungssatz bezeichnet wird , dass jede ganze Zahl größer als 1 eindeutig als Produkt von Primzahlen bis zur Ordnung der Faktoren dargestellt werden kann. Zum Beispiel,

${\displaystyle 1200=2^{4}\cdot 3\cdot 5^{2}=(2\cdot 2\cdot 2\cdot 2)\cdot 3\cdot (5\cdot 5)=5\cdot 2\ cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots }$

Der Satz sagt zwei Dinge über dieses Beispiel: Erstens, dass 1200 kann als Produkt von Primzahlen dargestellt werden, und zweitens, dass , egal wie dies geschehen ist, wird es immer genau vier 2s sein, ein 3, zwei 5s, und keine andere Primzahlen im Produkt.

Die Voraussetzung, dass die Faktoren Primzahlen sind, ist notwendig: Faktorisierungen, die zusammengesetzte Zahlen enthalten, dürfen nicht eindeutig sein (z. B. ). ${\displaystyle 12=2\cdot 6=3\cdot 4}$

Dieser Satz ist einer der Hauptgründe, warum 1 nicht als Primzahl angesehen wird : Wenn 1 eine Primzahl wäre, dann wäre die Faktorisierung in Primzahlen nicht eindeutig; zum Beispiel,${\displaystyle 2=2\cdot 1=2\cdot 1\cdot 1=\ldots }$

Euklids Originalversion

Buch VII, Sätze 30, 31 und 32 und Buch IX, Proposition 14 von Euclid ‚s Elemente sind im Wesentlichen die Aussage und den Nachweis des Fundamentalsatzes.

Wenn zwei Zahlen durch Multiplikation miteinander eine Zahl ergeben und jede Primzahl das Produkt misst, misst sie auch eine der ursprünglichen Zahlen.

—  Euklid, Elements Book VII , Proposition 30

(In der modernen Terminologie: Wenn eine Primzahl p das Produkt ab teilt , dann teilt p entweder a oder b oder beides.) Satz 30 wird als Euklids Lemma bezeichnet und ist der Schlüssel zum Beweis des Fundamentalsatzes der Arithmetik.

Jede zusammengesetzte Zahl wird durch eine Primzahl gemessen.

—  Euklid, Elements Book VII , Proposition 31

(In der modernen Terminologie: jede ganze Zahl, die größer als eins ist, wird gleichmäßig durch eine Primzahl geteilt.) Satz 31 wird direkt durch unendliche Abstammung bewiesen .

Jede Zahl ist entweder eine Primzahl oder wird durch eine Primzahl gemessen.

—  Euklid, Elements Book VII , Proposition 32

Satz 32 leitet sich von Satz 31 ab und beweist, dass die Zerlegung möglich ist.

Wenn eine Zahl die kleinste ist, die von Primzahlen gemessen wird, wird sie von keiner anderen Primzahl außer denjenigen gemessen, die sie ursprünglich gemessen haben.

—  Euklid, Elements Book IX , Proposition 14

(In der modernen Terminologie: ein kleinstes gemeinsames Vielfaches mehrerer Primzahlen ist kein Vielfaches einer anderen Primzahl.) Buch IX, Satz 14 leitet sich von Buch VII, Satz 30 ab und beweist teilweise, dass die Zerlegung eindeutig ist – ein kritischer Punkt notiert von André Weil . Tatsächlich sind in diesem Satz die Exponenten alle gleich eins, so dass für den allgemeinen Fall nichts gesagt wird.

Artikel 16 der Gauss ' Disquisitiones Arithmeticae ist eine frühe moderne Aussage und der Nachweis unter Verwendung modularer Arithmetik .

Anwendungen

Kanonische Darstellung einer positiven ganzen Zahl

Jede positive ganze Zahl n > 1 lässt sich auf genau eine Weise als Produkt von Primzahlen darstellen:

${\displaystyle n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod_{i=1}^ {k}p_{i}^{n_{i}}}$

wobei p ₁ < p ₂ < ... < p _k Primzahlen sind und n _i positive ganze Zahlen sind. Diese Darstellung wird im Allgemeinen auf alle positiven ganzen Zahlen einschließlich 1 erweitert, nach der Konvention, dass das leere Produkt gleich 1 ist (das leere Produkt entspricht k = 0).

Diese Darstellung wird die kanonische Darstellung von n oder die Standardform von n genannt . Zum Beispiel,

999 = 3 ³ × 37,

1000 = 2 ³ × 5 ³ ,

1001 = 7×11×13.

Die Faktoren p ⁰ = 1 können eingefügt werden, ohne den Wert von n zu ändern (zum Beispiel 1000 = 2 ³ × 3 ⁰ × 5 ³ ). Tatsächlich kann jede positive ganze Zahl eindeutig als unendliches Produkt über alle positiven Primzahlen dargestellt werden:

${\displaystyle n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod_{i=1}^{ \infty}p_{i}^{n_{i}},}$

wobei eine endliche Anzahl von n _i positive ganze Zahlen sind und der Rest null ist. Das Zulassen negativer Exponenten bietet eine kanonische Form für positive rationale Zahlen .

Rechenoperationen

Die kanonischen Darstellungen des Produkts, des größten gemeinsamen Teilers (GCD) und des kleinsten gemeinsamen Vielfachen (LCM) zweier Zahlen a und b können einfach durch die kanonischen Darstellungen von a und b selbst ausgedrückt werden :

${\displaystyle {\begin{alignedat}{2}a\cdot b&=2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3} +b_{3}}7^{a_{4}+b_{4}}\cdots &&=\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b )&=2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{ 3})}7^{\min(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\min(a_{i},b_{i})},\\ \operatorname {lcm} (a,b)&=2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\ max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\max(a_{i}, b_{i})}.\end{alignedat}}}$

Die ganzzahlige Faktorisierung , insbesondere von großen Zahlen, ist jedoch viel schwieriger als Rechenprodukte, GCDs oder LCMs. Daher haben diese Formeln in der Praxis nur begrenzten Nutzen.

Arithmetische Funktionen

Viele arithmetische Funktionen werden unter Verwendung der kanonischen Darstellung definiert. Insbesondere werden die Werte der additiven und multiplikativen Funktionen durch ihre Werte auf den Potenzen von Primzahlen bestimmt.

Nachweisen

Der Beweis verwendet das Lemma von Euklid ( Elemente VII, 30): Wenn eine Primzahl das Produkt zweier ganzer Zahlen teilt , muss sie mindestens eine dieser ganzen Zahlen teilen.

Existenz

Es muss gezeigt werden, dass jede ganze Zahl größer als 1 entweder eine Primzahl oder ein Produkt von Primzahlen ist. Erstens ist 2 eine Primzahl. Nehmen Sie dann durch starke Induktion an , dass dies für alle Zahlen größer als 1 und kleiner als n gilt . Wenn n eine Primzahl ist, gibt es nichts mehr zu beweisen. Ansonsten gibt es ganze Zahlen a und b , wobei n = ab und 1 < a ≤ b < n ist . Nach der Induktionshypothese sind a = p ₁ p ₂ ⋅⋅⋅ p _j und b = q ₁ q ₂ ⋅⋅⋅ q _k Produkte von Primzahlen. Aber dann ist n = ab = p ₁ p ₂ ⋅⋅⋅ p _j q ₁ q ₂ ⋅⋅⋅ q _k ein Produkt von Primzahlen.

Einzigartigkeit

Nehmen wir im Gegenteil an, es gibt eine ganze Zahl mit zwei verschiedenen Primfaktorzerlegungen. Sei n die kleinste solche ganze Zahl und schreibe n = p ₁ p ₂ ... p _j = q ₁ q ₂ ... q _k , wobei jedes p _i und q _i eine Primzahl ist. Wir sehen , dass p ₁ dividieren q ₁ q ₂ ... q _k , so S. ₁ teilt einige q _i von Euclid Lemma . Ohne Beschränkung der Allgemeinheit, sagen wir, p ₁ teilt q ₁ . Da p ₁ und q ₁ beide prim sind, folgt p ₁ = q ₁ . Wenn wir zu unseren Faktorisierungen von n zurückkehren , können wir diese beiden Faktoren aufheben, um zu dem Schluss zu kommen, dass p ₂ ... p _j = q ₂ ... q _{k ist} . Wir haben jetzt zwei verschiedene Primfaktorzerlegungen einer ganzen Zahl, die streng kleiner als n ist , was der Minimalität von n widerspricht .

Einzigartigkeit ohne Euklids Lemma

Der Fundamentalsatz der Arithmetik kann auch ohne das Lemma von Euklid bewiesen werden. Der folgende Beweis ist von Euklids Originalversion des Euklidischen Algorithmus inspiriert .

Angenommen, dies ist die kleinste positive ganze Zahl, die auf zwei verschiedene Arten das Produkt von Primzahlen ist. Dies impliziert übrigens, dass , falls vorhanden, eine zusammengesetzte Zahl größer als sein muss . Sag jetzt ${\displaystyle s}$${\displaystyle s}$${\displaystyle 1}$

${\displaystyle {\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}} }$

Jeder muss von jedem verschieden sein. Andernfalls, wenn sagen wir, würde es eine positive ganze Zahl geben , die kleiner als s ist und zwei verschiedene Primfaktorzerlegungen hat. Das kann man auch annehmen, indem man die beiden Faktorisierungen bei Bedarf vertauscht. ${\displaystyle p_{i}}$${\displaystyle q_{j}.}$${\displaystyle p_{i}=q_{j},}$${\displaystyle t=s/p_{i}=s/q_{j}}$${\displaystyle p_{1}<q_{1},}$

Einstellung und man hat Daraus folgt, dass ${\displaystyle P=p_{2}\cdots p_{m}}$${\displaystyle Q=q_{2}\cdots q_{n},}$${\displaystyle s=p_{1}P=q_{1}Q.}$

${\displaystyle (q_{1}-p_{1})Q=p_{1}(PQ)<s.}$

Da angenommen wurde, dass die positiven ganzen Zahlen kleiner als s eine eindeutige Primfaktorzerlegung haben, muss die Zerlegung von entweder oder Q erfolgen . Der letztere Fall ist unmöglich, da Q , kleiner als sein s , eine einzigartige Primfaktorzerlegung haben muss, und unterscheidet sich von jedem ersteren Fall ist auch nicht möglich, da, wenn ein Teiler von ist es muss auch ein Teiler von sein dem ist nicht möglich , da und sind verschiedene Primzahlen. ${\displaystyle p_{1}}$${\displaystyle q_{1}-p_{1}}$${\displaystyle p_{1}}$${\displaystyle q_{j}.}$${\displaystyle p_{1}}$${\displaystyle q_{1}-p_{1},}$${\displaystyle q_{1},}$${\displaystyle p_{1}}$${\displaystyle q_{1}}$

Daher kann es keine kleinste ganze Zahl mit mehr als einer einzigen unterschiedlichen Primfaktorzerlegung geben. Jede positive ganze Zahl muss entweder selbst eine Primzahl sein, die eindeutig faktorisieren würde, oder eine zusammengesetzte Zahl, die ebenfalls eindeutig in Primzahlen faktorisiert, oder im Fall der ganzen Zahl , keine Primzahl faktorisieren. ${\displaystyle 1}$

Verallgemeinerungen

Die erste Verallgemeinerung des Theorems findet sich in Gauß' zweiter Monographie (1832) über biquadratische Reziprozität . In dieser Arbeit wurde der sogenannte Ring der Gaußschen ganzen Zahlen eingeführt , die Menge aller komplexen Zahlen a + bi, wobei a und b ganze Zahlen sind. Es wird nun mit He gezeigt, dass dieser Ring die vier Einheiten ±1 und ± i hat , dass die von Null verschiedenen, nicht-einheitlichen Zahlen in zwei Klassen fallen, Primzahlen und Komposite, und dass (außer der Ordnung) die Komposite eindeutige Faktorisierung als Produkt von Primzahlen. ${\displaystyle \mathbb{Z} [i].}$

In ähnlicher Weise im Jahr 1844 , während auf Arbeits kubische Reziprozität , Eisenstein eingeführt , um den Ring , wo ein Würfel ist Einheitswurzel . Dies ist der Ring der Eisenstein-Ganzzahlen , und er hat bewiesen, dass er die sechs Einheiten hat und dass er eine eindeutige Faktorisierung hat. ${\displaystyle \mathbb{Z} [\omega]}$${\displaystyle \omega ={\frac {-1+{\sqrt {-3}}}{2}},}$   ${\displaystyle \omega ^{3}=1}$${\displaystyle \pm 1,\pm \omega ,\pm \omega ^{2}}$

Es wurde jedoch auch entdeckt, dass eine eindeutige Faktorisierung nicht immer gilt. Ein Beispiel liefert . In diesem Ring hat man ${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$

${\displaystyle 6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}).}$

Beispiele wie dieses führten dazu, dass der Begriff "prime" modifiziert wurde. Darin kann bewiesen werden, dass, wenn einer der obigen Faktoren als Produkt dargestellt werden kann, zum Beispiel 2 = ab , einer von a oder b eine Einheit sein muss. Dies ist die traditionelle Definition von "prime". Es kann auch bewiesen werden, dass keiner dieser Faktoren dem Lemma von Euklid gehorcht; zum Beispiel teilt 2 weder (1 + √ −5 ) noch (1 − √ −5 ), obwohl es deren Produkt 6 teilt. In der algebraischen Zahlentheorie heißt 2 irreduzibel in (nur durch sich selbst oder eine Einheit teilbar), aber nicht prim in (wenn es ein Produkt teilt, muss es einen der Faktoren teilen). Die Erwähnung von ist erforderlich, da 2 eine Primzahl und irreduzibel ist. Mit diesen Definitionen kann bewiesen werden, dass in jedem ganzzahligen Bereich eine Primzahl irreduzibel sein muss. Euklids klassisches Lemma kann umformuliert werden als "im Ring der ganzen Zahlen ist jede irreduzible Primzahl". Dies gilt auch in und aber nicht in${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$${\displaystyle\mathbb{Z}.}$${\displaystyle \mathbb{Z}}$${\displaystyle \mathbb{Z} [i]}$${\displaystyle \mathbb{Z} [\omega],}$${\displaystyle \mathbb {Z} [{\sqrt {-5}}].}$

Die Ringe, in denen die Faktorisierung in Irreduziblen im Wesentlichen eindeutig ist, werden als eindeutige Faktorisierungsdomänen bezeichnet . Wichtige Beispiele sind Polynomringe über den ganzen Zahlen oder über einem Körper , euklidische Gebiete und prinzipielle Idealgebiete .

1843 führte Kummer den von Dedekind (1876) weiterentwickelten Begriff der idealen Zahl in die moderne Theorie der Ideale , spezieller Teilmengen von Ringen, ein. Multiplikation ist für Ideale definiert, und die Ringe, in denen sie eine eindeutige Faktorisierung aufweisen, werden Dedekind-Domänen genannt .

Es gibt eine Version der eindeutigen Faktorisierung für Ordinalzahlen , die jedoch einige zusätzliche Bedingungen erfordert, um die Eindeutigkeit sicherzustellen.

Siehe auch

• Integer Factorization  – Zerlegung einer ganzen Zahl in ein Produkt
• Prime Unterschrift  - Multiset von prime Exponenten in einer Primfaktorzerlegung

Anmerkungen

Verweise

Die Disquisitiones Arithmeticae wurde aus dem Lateinischen ins Englische und Deutsche übersetzt. Die deutsche Ausgabe enthält alle seine Aufsätze zur Zahlentheorie: alle Beweise der quadratischen Reziprozität, die Vorzeichenbestimmung der Gaußsumme, die Untersuchungen zur biquadratischen Reziprozität und unveröffentlichte Notizen.

• Gauß, Carl Friedrich; Clarke, Arthur A. (Übersetzer ins Englische) (1986), Disquisitiones Arithemeticae (zweite, korrigierte Auflage) , New York: Springer , ISBN 978-0-387-96254-2
• Gauß, Carl Friedrich; Maser, H. (Übersetzer ins Deutsche) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number Theory) (Zweite Auflage) , New York: Chelsea, ISBN 0-8284-0191-8

Die beiden von Gauß veröffentlichten Monographien zur biquadratischen Reziprozität haben fortlaufend nummerierte Abschnitte: die erste enthält die §§ 1–23 und die zweite die §§ 24–76. Darauf verweisende Fußnoten haben die Form „Gauss, BQ, § n “. Fußnoten zu den Disquisitiones Arithmeticae haben die Form „Gauss, DA, Art. n “.

• Gauß, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima , Göttingen: Kommentar. Soz. regiae sci, Göttingen 6
• Gauß, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda , Göttingen: Kommentar. Soz. regiae sci, Göttingen 7

Diese sind in Gauss' Werken , Band II, S. 65–92 und 93–148; Deutsche Übersetzungen sind S. 511–533 und 534–586 der deutschen Ausgabe der Disquisitiones .

• Baker, Alan (1984), Eine kurze Einführung in die Zahlentheorie , Cambridge, UK: Cambridge University Press, ISBN 978-0-521-28654-1
• Euclid (1956), Die dreizehn Bücher der Elemente , 2 (Bücher III-IX), Übersetzt von Thomas Little Heath (Zweite Ausgabe Ungekürzte Ausgabe), New York: Dover , ISBN 978-0-486-60089-5
• Hardy, GH ; Wright, EM (2008) [1938]. Eine Einführung in die Zahlentheorie . Überarbeitet von DR Heath-Brown und JH Silverman . Vorwort von Andrew Wiles . (6. Aufl.). Oxford: Oxford University Press . ISBN 978-0-19-921986-5. MR  2.445.243 . Zbl  1159.11001 .
• A. Kornilowicz; P. Rudnicki (2004), "Grundsatz der Arithmetik", Formalized Mathematics , 12 (2): 179–185
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2. Aufl.), Lexington: DC Heath and Company , LCCN  77-171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elemente der Zahlentheorie , Englewood Cliffs: Prentice Hall , LCCN  77-81766.
• Riesel, Hans (1994), Primzahlen und Computermethoden zur Faktorisierung (zweite Auflage) , Boston: Birkhäuser, ISBN 0-8176-3743-5
• Weil, André (2007) [1984]. Zahlentheorie: Ein Ansatz durch die Geschichte von Hammurapi bis Legendre . Moderne Birkhäuser Klassiker. Boston, MA: Birkhäuser. ISBN 978-0-817-64565-6.
• Weisstein, Eric W. "Abnormale Zahl" . MathWorld .
• Weisstein, Eric W. "Grundsatz der Arithmetik" . MathWorld .

Externe Links

• Warum ist der fundamentale Satz der Arithmetik nicht offensichtlich?
• GCD und das Fundamental Theorem of Arithmetic at cut-the-knot .
• PlanetMath: Beweis des Fundamentalsatzes der Arithmetik
• Fermat's Last Theorem Blog: Unique Factorization , ein Blog, das die Geschichte von Fermats letztem Theorem von Diophantus von Alexandria bis zum Beweis von Andrew Wiles behandelt .
• "Fundamental Theorem of Arithmetic" von Hector Zenil, Wolfram Demonstrations Project , 2007.
• Grim, James. "1 und Primzahlen" . Zahlenphil . Brady Haran .