In der Zahlentheorie stellt der Hauptsatz der Arithmetik (oder der unique-prime-factorization Lehrsatz) fest, dass jede ganze Zahl, die größer ist als 1, als ein einzigartiges Produkt (bis zur Einrichtung der Faktoren) von Primzahlen geschrieben werden kann. Zum Beispiel,

::

sind zwei Zahlen, die die Hypothese des Lehrsatzes befriedigen, der als das Produkt von Primzahlen geschrieben werden kann.

Der Beweis der Existenz eines ersten factorization ist aufrichtig; der Beweis der Einzigartigkeit ist schwieriger. Einige Beweise verwenden die Tatsache dass, wenn eine Primzahl p das Produkt von zwei natürlichen Zahlen a und b teilt, dann teilt p entweder a oder b, eine als das Lemma von Euklid bekannte Behauptung. Da die Multiplikation auf den ganzen Zahlen sowohl auswechselbar als auch assoziativ ist, ist es nicht von Bedeutung, auf welche Weise wir eine Zahl schreiben, die größer ist als 1 als das Produkt der Blüte; es ist üblich, die (ersten) Faktoren in der Ordnung von kleinsten zum größten zu schreiben.

Einige natürliche Erweiterungen der Hypothese dieses Lehrsatzes erlauben jeder ganzen Nichtnullzahl, als das Produkt von "Primzahlen" und "invertibles" ausgedrückt zu werden. Zum Beispiel, 1 und 1 werden erlaubt, Faktoren solcher Darstellungen zu sein (obwohl, wie man betrachtet, sie nicht erst sind). Auf diese Weise kann man den Hauptsatz der Arithmetik zu jedem Euklidischen Gebiet oder idealem Hauptgebiet erweitern, das an bestimmte Modifizierungen zur Hypothese des Lehrsatzes denkt. Ein Ring, in dem der Hauptsatz der Arithmetik hält, wird ein einzigartiges factorization Gebiet genannt.

Viele Autoren nehmen 1 an, eine natürliche Zahl zu sein, die keinen ersten factorization hat. So behauptet Lehrsatz 1 dessen nimmt die Form an, "Ist jede positive ganze Zahl, außer 1, ein Produkt von einer oder mehr Blüte," und Lehrsatz 2 (ihr "Grundsätzliches") Einzigartigkeit. Durch die Tagung ist die Nummer 1 nicht selbst erst, aber da es das Produkt keiner Zahlen ist, ist es häufig günstig, es in den Lehrsatz durch die leere Produktregel einzuschließen. (Sieh zum Beispiel, das Rechnen des gcd.)

Anwendungen

Der Hauptsatz der Arithmetik gründet die Wichtigkeit von Primzahlen. Primzahlen sind die grundlegenden Bausteine jeder positiven ganzen Zahl im Sinn, dass jede positive ganze Zahl vom Produkt der Blüte mit einem einzigartigem Aufbau gebaut werden kann. Die Entdeckung des ersten factorization einer ganzen Zahl erlaubt Abstammung aller seiner Teiler, sowohl erst als auch nichterst. Dieses Eigentum der Einzigartigkeit ist stark, weil vom factorization als ein Schlüssel für eine Zahl gedacht werden kann. Das ist, warum es verwendet werden kann, um starke Verschlüsselungstechniken wie RSA zu bauen.

Zum Beispiel, der obengenannte factorization 6936 Shows, dass jeder positive Teiler 6936 die Form 2 × 3 × 17 haben muss, wo ein Annehmen von einem der 4 Werte {0, 1, 2, 3}, wo b einen der 2 Werte {0, 1} annimmt, und wo c einen der 3 Werte {0, 1, 2} annimmt. Das Multiplizieren der Zahlen von unabhängigen Optionen erzeugt zusammen insgesamt 4 × 2 × 3 = 24 positive Teiler.

Sobald die ersten factorizations von zwei Zahlen bekannt sind, können ihr größter allgemeiner Teiler und kleinstes Gemeinsames Vielfaches schnell gefunden werden. Zum Beispiel vom obengenannten wird es gezeigt, dass der größte allgemeine Teiler 6936 und 1200 2 × 3 = 24 ist. Jedoch, wenn die ersten factorizations nicht bekannt sind, verlangt der Gebrauch des Euklidischen Algorithmus allgemein viel weniger Berechnung als Factoring die zwei Zahlen.

Der Hauptsatz stellt sicher, dass Zusatz und multiplicative arithmetische Funktionen durch ihre Werte auf den Mächten von Primzahlen völlig bestimmt werden.

Es kann wichtig sein zu bemerken, dass Ägypter wie Ahmes frühere praktische Aspekte des Factorings, solcher als kleinstes Gemeinsames Vielfaches verwendet haben, einer langen Tradition erlaubend, sich, wie formalisiert, durch Euklid, und streng bewiesen von Carl Friedrich Gauss zu entwickeln.

Obwohl auf den ersten Blick der Lehrsatz 'offensichtlich' scheint, hält er in allgemeineren Zahl-Systemen einschließlich vieler Ringe von algebraischen ganzen Zahlen nicht. Darauf wurde zuerst von Ernst Kummer 1843 in seiner Arbeit am Letzten Lehrsatz von Fermat hingewiesen. Die Anerkennung dieses Misserfolgs ist eine der frühsten Entwicklungen in der Theorie der algebraischen Zahl.

Der Beweis von Euklid

Der Beweis besteht aus zwei Schritten. Im ersten Schritt, wie man zeigt, ist jede Zahl ein Produkt der Null oder mehr Blüte. Im zweiten Schritt zeigt der Beweis, dass irgendwelche zwei Darstellungen in eine einzelne Darstellung vereinigt werden können.

Zerlegbare Nichthauptzahlen

Beweis durch den Widerspruch über das minimale Gegenbeispiel: Nehmen Sie An, dass es positive ganze Zahlen gab, die als ein Produkt der Blüte nicht geschrieben werden können. Dann durch den gut bestellenden Grundsatz muss es einen kleinsten solche Zahl, n geben. Wegen der Tagung des leeren Produktes oben kann n nicht 1 sein. Außerdem kann n keine Primzahl sein, da jede Primzahl ein Produkt einer einzelnen Blüte ist: selbst. So muss n eine zerlegbare Zahl sein. So

:

wo sowohl a als auch b positive ganze Zahlen sind, die kleiner sind als n. Da n die kleinste Zahl ist, die als ein Produkt der Blüte nicht geschrieben werden kann, können sowohl a als auch b als Produkte der Blüte geschrieben werden. Aber dann

:

kann als ein Produkt der Blüte ebenso, einfach durch das Kombinieren des factorizations von a und b geschrieben werden; aber das widerspricht unserer Annahme. Folglich können alle positiven ganzen Zahlen als ein Produkt der Blüte geschrieben werden.

Beweis der Einzigartigkeit

Der Schlüsselschritt im Beweis der Einzigartigkeit ist

Der Vorschlag von Euklid 30 des Buches 7 (bekannt als das Lemma von Euklid), der dass, für jede Primzahl p und irgendwelche natürlichen Zahlen a, b feststellt: Wenn sich p teilt, ab dann teilt p a, oder p teilt b.

Das kann wie folgt bewiesen werden:

• Nehmen Sie an, dass ein erster p ab teilt (wo a, b natürliche Zahlen sind), aber teilt a nicht. Wir müssen beweisen, dass p b teilt.
• Da p a nicht teilt, und p, der größte allgemeine Teiler von p erst ist und zu sein.
• Durch die Identität von Bézout, hieraus folgt dass für einige ganze Zahlen x, y (vielleicht negativ),
• Beide Seiten mit b, multiplizierend
• Da sich p teilt, teilt p
• Da p beide teilt, welcher summands links, p b teilt.

Ein Beweis der Einzigartigkeit des ersten factorization einer gegebenen ganzen Zahl geht wie folgt weiter.

Lassen Sie s die kleinste natürliche Zahl sein, die als (mindestens) zwei verschiedene Produkte von Primzahlen geschrieben werden kann. Zeigen Sie diese zwei factorizations von s als p an ··· p und q ··· q, solch dass s = Seiten ··· p = qq ··· q.

Sowohl q als auch q ··· q muss einzigartigen ersten factorizations haben (da beide kleiner sind als s). Durch den Vorschlag von Euklid teilt entweder p q, oder p teilt q ··· q. Deshalb p = q (für einen j). Aber indem wir p und q von der anfänglichen Gleichwertigkeit umziehen, haben wir eine kleinere ganze Zahl factorizable auf zwei Weisen, unserer anfänglichen Annahme widersprechend. Deshalb kann es keinen solchen s geben, und alle natürlichen Zahlen haben einen einzigartigen ersten factorization.

Kanonische Darstellung einer positiven ganzen Zahl

Da die Hauptfaktoren einer ganzen Zahl nicht verschieden zu sein brauchen, folgt sie aus dem Hauptsatz der Arithmetik, dass jede ganze Zahl n> 1 auf genau eine Weise als ein Produkt von Hauptmächten (1 entsprechend dem leeren Produkt) vertreten werden kann

:

n

p_1^ {\\alpha_1} p_2^ {\\alpha_2} \cdots p_k^ {\\alpha_k }\

\prod_ {ich

1\^ {k} p_i^ {\\alpha_i }\

</Mathematik>

wo p Blüte sind und die α positive ganze Zahlen sind.

Diese Darstellung wird die kanonische Darstellung von n oder die Standardform von n genannt. Z.B, 12 = 2 · 3, 1296 = 2 · 3, und 220 = 2 · 5 · 11.

Wenn, in einem gegebenen Problem, nur eine Zahl auf diese Weise vertreten wird, verlangen wir gewöhnlich, dass α für jeden ich als oben positiv ist. Jedoch für die notational Bequemlichkeit, wenn zwei oder mehr Zahlen beteiligt werden, erlauben wir manchmal einigen der Hochzahlen, Null zu sein. Wenn α = 0, zum Beispiel, der erste p einfach in der kanonischen Darstellung von n nicht vorkommt. Dieses Gerät macht es möglich, die kanonische Darstellung irgendwelcher zwei positiven ganzen Zahlen zu schreiben, so dass sie scheinen, dieselben Hauptfaktoren einzuschließen, wenn auch sie tatsächlich scheitern können, jeden nichttrivialen gemeinsamen Faktor zu haben. Zum Beispiel konnten wir 12 = 2 schreiben · 3 · 5 und 20 = 2 · 3 · 5. Und man konnte sogar 1 = 2 schreiben · 3 · 5.

Das kann ein bisschen weiter genommen werden: Jede ganze Zahl kann als ein unendliches Produkt übernommen alle Primzahlen, einzigartig vertreten werden

:

N=2^ {n_2} 3^ {n_3} 5^ {n_5} 7^ {n_7 }\\cdots =\prod p_i^ {n_ {p_i}}.

</Mathematik>

wo alle außer einer begrenzten Zahl des n Null sind. (1 entsprechend dem ganzen n Null zu sein.) Diese Darstellung ist für Ausdrücke wie diese für das Produkt, gcd, und lcm günstig:

:

a\cdot b

2^ {a_2+b_2 }\\, 3^ {a_3+b_3 }\\, 5^ {a_5+b_7 }\\, 7^ {a_7+b_7 }\\cdots

\prod p_i^ {a_ {p_i} +b_ {p_i}},

</Mathematik>:

\gcd (a, b)

2^ {\\Minute (a_2, b_2) }\\, 3^ {\\Minute (a_3, b_3) }\\, 5^ {\\Minute (a_5, b_5) }\\, 7^ {\\Minute (a_7, b_7) }\\cdots

\prod p_i^ {\\Minute (a_ {p_i}, b_ {p_i})},

</Mathematik>:

\operatorname {lcm} (a, b)

2^ {\\max (a_2, b_2) }\\, 3^ {\\max (a_3, b_3) }\\, 5^ {\\max (a_5, b_5) }\\, 7^ {\\max (a_7, b_7) }\\cdots

\prod p_i^ {\\max (a_ {p_i}, b_ {p_i})}.

</Mathematik>

Generalisationen

Der Hauptsatz der Arithmetik verallgemeinert zu verschiedenen Zusammenhängen; zum Beispiel im Zusammenhang der Ringtheorie, wo sich das Feld der Theorie der algebraischen Zahl entwickelt. Wie man sagt, ist ein Ring ein einzigartiges factorization Gebiet, wenn der Hauptsatz der Arithmetik (für Nichtnullelemente) dort hält. Zum Beispiel sind jedes Euklidische Gebiet oder ideales Hauptgebiet notwendigerweise ein einzigartiges factorization Gebiet. Spezifisch ist ein Feld trivial ein einzigartiges factorization Gebiet.

Siehe auch

• Teiler-Funktion
• Hauptsatz der Algebra
• Hauptsatz der Rechnung
• Ganze Zahl factorization
• Hauptunterschrift
• Einzigartiges factorization Gebiet

Referenzen

. .

• A. Korni lowicz und P. Rudnicki. Hauptsatz der Arithmetik. Formalisierte Mathematik, 12 (2):179-185, 2004.

Außenverbindungen

• GCD und der Hauptsatz der Arithmetik an der Knoten-Kürzung
• PlanetMath: Beweis des Hauptsatzes der Arithmetik
• Der letzte Lehrsatz von Fermat Blog: Einzigartiger Factorization, Ein blog, der die Geschichte des Letzten Lehrsatzes von Fermat von Diophantus Alexandrias zum Beweis durch Andrew Wiles bedeckt.
• "Hauptsatz der Arithmetik" durch Hector Zenil, Wolfram-Demonstrationsprojekt, 2007.