Euklids Lemma - Euclid's lemma

In der Zahlentheorie ist das Lemma von Euklid ein Lemma , das eine grundlegende Eigenschaft von Primzahlen erfasst , nämlich:

Wenn beispielsweise p = 19 , a = 133 , b = 143 , dann ab = 133 × 143 = 19019 ist , und da dies durch 19 teilbar ist, impliziert das Lemma, dass auch eines oder beide von 133 oder 143 sein müssen. Tatsächlich ist 133 = 19 × 7 .

Wenn die Prämisse des Lemmas nicht gilt, dh p eine zusammengesetzte Zahl ist , kann seine Konsequenz entweder wahr oder falsch sein. Zum Beispiel im Fall von p = 10 , a = 4 , b = 15 , die zusammengesetzte Zahl 10 teilt ab = 4 × 15 = 60 , aber 10 teilt weder 4 noch 15.

Diese Eigenschaft ist der Schlüssel zum Beweis des Fundamentalsatzes der Arithmetik . Es wird verwendet, um Primzahlen zu definieren , eine Verallgemeinerung von Primzahlen auf beliebige kommutative Ringe . Das Lemma von Euklid zeigt, dass in den ganzen Zahlen irreduzible Elemente auch Primelemente sind. Der Beweis verwendet Induktion, also gilt er nicht für alle ganzzahligen Gebiete .

Formulierungen

Sei eine Primzahl und teile das Produkt zweier ganzer Zahlen und . In Symbolen wird dies geschrieben . Seine Negation, teilt nicht , steht geschrieben . Dann oder (oder beides). Äquivalente Aussagen sind: ${\displaystyle p}$${\displaystyle p}$${\displaystyle a}$${\displaystyle b}$${\displaystyle p\mid ab}$${\displaystyle p}$${\displaystyle ab}$${\displaystyle p\nmid ab}$${\displaystyle p\mid a}$${\displaystyle p\mid b}$

• Wenn und , dann .${\displaystyle p\nmitte a}$${\displaystyle p\nmid b}$${\displaystyle p\nmid ab}$
• Wenn und , dann .${\displaystyle p\nmitte a}$${\displaystyle p\mid ab}$${\displaystyle p\mid b}$

Das Lemma von Euklid kann von Primzahlen auf beliebige ganze Zahlen verallgemeinert werden:

Dies ist eine Verallgemeinerung, denn wenn entweder eine Primzahl ist ${\displaystyle n}$

• ${\displaystyle n\mid a}$ oder
• ${\displaystyle n}$ist relativ prim zu . Bei dieser zweiten Möglichkeit, also .${\displaystyle a}$${\displaystyle n\nmitte a}$${\displaystyle n\mid b}$

Geschichte

Das Lemma erscheint zunächst als Proposition 30 in Buch VII von Euklid ‚s Elemente . Es ist in praktisch jedem Buch enthalten, das die elementare Zahlentheorie behandelt.

Die Verallgemeinerung des Lemmas auf ganze Zahlen erschien 1681 in Jean Prestets Lehrbuch Nouveaux Elémens de Mathématiques .

In Carl Friedrich Gauß ' Abhandlung Disquisitiones Arithmeticae ist die Aussage des Lemmas Euklids Satz 14 (Abschnitt 2), mit dem er die Eindeutigkeit des Zerlegungsprodukts von Primfaktoren einer ganzen Zahl (Satz 16) beweist und die Existenz als "offensichtlich". Aus dieser Existenz und Eindeutigkeit leitet er dann die Verallgemeinerung der Primzahlen auf ganze Zahlen ab. Aus diesem Grund wird die Verallgemeinerung des Euklid-Lemmas manchmal als Gauß-Lemma bezeichnet, aber einige glauben, dass diese Verwendung aufgrund der Verwechslung mit dem Gauß-Lemma auf quadratischen Resten falsch ist .

Nachweisen

Nachweis über die Identität von Bézout

In der modernen Mathematik beinhaltet ein üblicher Beweis ein Ergebnis namens Bézouts Identität , das zu Euklids Zeit unbekannt war. Bézout Identität besagt , dass , wenn x und y sind relativ prime ganze Zahlen (dh sie anderen keine gemeinsamen Teiler teilen als 1 und -1) gibt es ganze Zahlen r und s , so dass

${\displaystyle rx+sy=1.}$

Seien a und n teilerfremd und n | ab . Bei Bézouts Identität gibt es R und S Making

${\displaystyle rn+sa=1.}$

Beide Seiten mit b multiplizieren :

${\displaystyle rnb+sab=b.}$

Der erste Term auf der linken Seite ist durch n teilbar , und der zweite Term ist durch ab teilbar , das hypothetisch durch n teilbar ist . Daher ist ihre Summe b auch durch n teilbar . Dies ist die Verallgemeinerung des oben erwähnten Lemmas von Euklid.

Direkter Beweis

Der folgende Beweis ist von Euklids Version des Euklidischen Algorithmus inspiriert , der nur mit Subtraktionen vorgeht.

Angenommen, und . Das wollen wir zeigen . Da gibt es eine n- Primzahl zu a (d. h. ihre einzigen gemeinsamen Teiler sind 1 und –1 ), so dass ${\displaystyle p\nmitte a}$${\displaystyle p\mid ab}$${\displaystyle p\mid b}$${\displaystyle p\nmitte a}$

${\displaystyle nq=ab.}$

Man muss beweisen, dass n Teiler von b ist . Um dies durch starke Induktion zu beweisen , nehmen wir an, dass dies für alle positiven unteren Werte von ab bewiesen ist .

Es gibt drei Fälle:

Wenn n = a , impliziert Koprimalität n = 1 , und n teilt b trivial.

Wenn n < a , hat man

${\displaystyle n(qb)=(an)b.}$

Die positiven ganzen Zahlen a – n und n sind teilerfremd: Wenn eine Primzahl beide teilt, dann teilt sie ihre Summe und teilt somit sowohl n als auch a . Dies ist ein Widerspruch zur Koprimalitätshypothese. Als Folge der rechten Seite ist q – b positiv. Die Schlussfolgerung folgt also aus der Induktionshypothese, da a – n < a .

Wenn n > a , hat man

${\displaystyle (na)q=a(bq).}$

Ähnlich wie oben sind n – a und a teilerfremd. Da b - q < b , durch die Induktions Hypothese, gibt es eine ganze Zahl r , so dass also ${\displaystyle bq=r(na).}$

${\displaystyle (na)q=a(bq)=ar(na),}$

und man erhält q = ar , indem man durch n – a dividiert . Somit und durch Division durch a erhält man b = nr , was die gewünschte Schlussfolgerung ist. ${\displaystyle ab=nq=anr,}$

Nachweis der Elemente

Das Lemma von Euklid wird in Proposition 30 in Buch VII von Euklids Elementen bewiesen . Der Originalbeweis ist so wie er ist schwer zu verstehen, daher zitieren wir den Kommentar von Euclid (1956 , S. 319–332).

Vorschlag 19

Wenn vier Zahlen proportional sind, ist die Zahl aus der ersten und vierten gleich der Zahl aus der zweiten und dritten; und wenn die aus der ersten und vierten erzeugte Zahl gleich der aus der zweiten und dritten erzeugten Zahl ist, sind die vier Zahlen proportional.

Vorschlag 20

Die kleinste Anzahl derer, die das gleiche Verhältnis haben, misst diejenigen, die das gleiche Verhältnis haben, gleich oft – je größer, desto größer und je kleiner, desto kleiner.

Vorschlag 21

Zahlen, die zueinander prim sind, sind die kleinsten, die das gleiche Verhältnis zu ihnen haben.

Vorschlag 29

Jede Primzahl ist eine Primzahl zu jeder Zahl, die sie nicht misst.

Vorschlag 30

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

Nachweis von 30

Wenn c eine Primzahl ist, misst man ab , c misst entweder a oder b .
Es sei c nicht messen ein .
Daher sind c , a zueinander prim.[ VII. 29 ]
Nehmen wir ab = mc .
Daher c  : ein = b : m . [ VII. 19］
Daher VII. 20 , 21 ] b = nc , wobei n einige ganze Zahl ist.
Daher misst c b .
Wenn c nicht b misst , misst c analog a .
Daher misst c die eine oder andere der beiden Zahlen a , b .
QED

Siehe auch

Fußnoten

Anmerkungen

Zitate

Verweise

• Bajnok, Béla (2013), An Invitation to Abstract Mathematics , Undergraduate Texts in Mathematics , Springer, ISBN 978-1-4614-6636-9.
• Euclid (1956), Die dreizehn Bücher der Elemente , Bd. 2 (Bücher III-IX), übersetzt von Heath, Thomas Little , Dover Publications, ISBN 978-0-486-60089-5 |volume=hat zusätzlichen Text ( Hilfe )- vol. 2
• Euclid (1994), Les Éléments, traduction, commentaires et notes (auf Französisch), 2 , übersetzt von Vitrac, Bernard, S. 338–339, ISBN 2-13-045568-9
• Gauss, Carl Friedrich (2001), Disquisitiones Arithmeticae , übersetzt von Clarke, Arthur A. (zweite, korrigierte Hrsg.), New Haven, CT: Yale University Press, ISBN 978-0-300-09473-2
• Gauss, Carl Friedrich (1981), Untersuchungen über höhere Arithmetik [ Untersuchungen zur höheren Arithmetik ], übersetzt von Maser, = H. (Zweite Aufl.), New York: Chelsea, ISBN 978-0-8284-0191-3
• Hardy, GH ; Wright, EM ; Wiles, AJ (2008-09-15), An Introduction to the Theory of Numbers (6. Aufl.), Oxford: Oxford University Press , ISBN 978-0-19-921986-5
• Irland, Kenneth; Rosen, Michael (2010), A Classical Introduction to Modern Number Theory (Zweite Aufl.), New York: Springer , ISBN 978-1-4419-3094-1
• Joyner, David; Kreminski, Richard; Turisco, Joann (2004), Angewandte Abstrakte Algebra , JHU Press, ISBN 978-0-8018-7822-0.
• Landau, Edmund ; Goodman, JE (Übersetzer ins Englische) (1999), Elementary Number Theory (2. Aufl.), Providence, Rhode Island: American Mathematical Society, ISBN 978-0-821-82004-9
• Martin, GE (2012), The Foundations of Geometry and the Non-Euclidean Plane , Undergraduate Texts in Mathematics, Springer, ISBN 978-1-4612-5725-7.
• Riesel, Hans (1994), Primzahlen und Computermethoden zur Faktorisierung (2. Aufl.), Boston: Birkhäuser, ISBN 978-0-8176-3743-9.

Externe Links

• Weisstein, Eric W. "Euklids Lemma" . MathWorld .