Ganze Zahlen

Original: http://www.efgh.com/math/algebra/integers.htm von Philip J. Erdelsky

1. Charakterisierung der ganzen Zahlen

Die Menge Z + der positiven ganzen Zahlen {1, 2, 3, …} ist einfach und vertraut, aber sie auf eine völlig rigorose Weise zu beschreiben, ist nicht trivial. Viele unserer Theoreme werden so offensichtlich erscheinen, dass sie keinen Beweis erfordern sollten.

Wie immer in der Mathematik müssen wir mit einigen Postulaten beginnen. Wir versuchen, einen minimalen Satz der einfachsten und offensichtlichsten Merkmale der ganzen Zahlen zu wählen.

Einige Eigenschaften der positiven ganzen Zahlen sind leicht anzugeben. Jeder positiven Ganzzahl folgt eine weitere positive Ganzzahl, die als Nachfolger bezeichnet wird. Die Zahl 1 ist die erste positive ganze Zahl, also ist sie nicht der Nachfolger einer anderen positiven Zahl. Jede weitere positive ganze Zahl ist der Nachfolger von einer und nur einer positiven ganzen Zahl.

Der Nachfolger von n wird als n+1 geschrieben. Allerdings haben wir an dieser Stelle keine andere Art von Addition definiert.

Wir können 2 streng als 1+1, 3 als 2+1, etc. definieren und die Sequenz nur so weit fortsetzen, wie es für eine bestimmte Diskussion erforderlich ist.

Eine weitere Eigenschaft ist erforderlich, da es Zahlensysteme gibt, die sich von den positiven ganzen Zahlen unterscheiden, die alle diese Eigenschaften aufweisen. Ein solches System besteht aus den positiven ganzen Zahlen mit der üblichen Nachfolgerbeziehung sowie zwei zusätzlichen Elementen A und B, die Nachfolger voneinander sind.

Die zusätzliche Eigenschaft ist eine, die besagt, dass jede positive ganze Zahl 1 oder 2 oder 3 oder 4 ist, und so weiter auf unbestimmte Zeit. Leider hat „und so weiter auf unbestimmte Zeit“ keinen Platz in einer strengen Definition, auch wenn wir denken mögen, dass wir wissen, was es bedeutet.

Glücklicherweise gibt es eine Alternative.

Eine Teilmenge von Z + gilt als unter Nachfolge geschlossen, wenn sie die Nachfolger aller ihrer Elemente enthält; das heißt, wenn n in der Teilmenge ist, dann ist n+1 auch in der Teilmenge. Zum Beispiel wird {1, 2} nicht unter Nachfolge geschlossen, sondern {3, 4, 5, 5, …}.

Jetzt können wir die endgültige erforderliche Eigenschaft der positiven ganzen Zahlen angeben: Jede Teilmenge von Z +, die 1 enthält und unter Nachfolge geschlossen wird, enthält alle positiven ganzen Zahlen.

Eigentlich können wir mit etwas schwächeren Bedingungen auskommen, die als Peano-Postulate bezeichnet werden:

Jede positive ganze Zahl hat einen Nachfolger.
Die Zahl 1 ist nicht der Nachfolger einer positiven ganzen Zahl.
Jede positive ganze Zahl, die von 1 verschieden ist, ist der Nachfolger von höchstens einer positiven ganzen Zahl.
Jeder Satz positiver Ganzzahlen, der 1 enthält und unter Nachfolge geschlossen wird, enthält alle positiven Ganzzahlen.

Zwei weitere ziemlich offensichtliche Eigenschaften der positiven ganzen Zahlen können als Theorem nachgewiesen werden.

Satz 1.1. Jede positive ganze Zahl außer 1 ist der Nachfolger von genau einer positiven ganzen Zahl, und keine positive ganze Zahl ist ihr eigener Nachfolger.

Beweis. Nehmen wir zum Zwecke des Widerspruchs an, dass die positive ganze Zahl n von 1 verschieden ist und nicht der Nachfolger einer positiven ganzen Zahl oder ihr eigener Nachfolger ist. Dann verletzt die Menge Z + – {n} in beiden Fällen das Peano-Postulat (4). ?

Der Satz 1.1 kann auch prägnanter formuliert werden. Die Nachfolgefunktion f(n) = n+1 ist ein Eins-zu-Eins-Mapping von Z + auf Z + + – {1}.

Es ist jetzt einfach zu zeigen, dass 1, 2, 3 und 4 alle unterschiedlich sind. Wenn 1 = 2, 1 = 3 oder 1 = 4 ist, dann wäre 1 der Nachfolger von 1, 2 oder 3. Wenn 2 = 3 oder 3 = 4, dann wären 2 oder 3 sein eigener Nachfolger. Wenn 2 = 4 dann 1 = 3, weil jede ganze Zahl der Nachfolger von nur einer ganzen Zahl ist, und 1 = 3 bereits ausgeschlossen wurde. Ähnliche Argumente können für eine beliebige Anzahl von ganzen Zahlen verwendet werden, die aufgelistet und vollständig behandelt werden können.

Wir haben noch keine Subtraktion definiert, aber für eine positive ganze Zahl n außer 1 werden wir die Notation n-1 verwenden, um die ganze Zahl zu bezeichnen, deren Nachfolger n ist.

2. Induktion und Rekursion

Peano Postulat (4) wird oft als mathematisches Induktionspostulat bezeichnet, da es in diese Form gegossen werden kann.

Die Technik der mathematischen Induktion besteht aus zwei Schritten. Nehmen Sie eine Aussage über die ganze Zahl n vor.

Schritt 1: Beweisen Sie die Aussage für n = 1.
Schritt 2: Angenommen, die Aussage ist wahr für n und dann beweisen Sie sie für n+1.

Die Anweisung muss dann für alle positiven Ganzzahlen gelten. In Schritt 2 wird die Annahme, dass die Aussage für n wahr ist, oft als induktive Hypothese bezeichnet. Die Technik wird durch den folgenden Satz formal begründet.

Satz 2.1. Lassen Sie S eine Aussage über eine positive ganze Zahl sein, und nehmen Sie an, dass

S ist wahr für 1,
für alle n, wenn S für n wahr ist, dann ist es für n+1 wahr.

Dann gilt S für alle positiven Ganzzahlen.

Beweis. Sei T die Menge aller positiven ganzen Zahlen, für die S wahr ist. Dann behauptet Peano Postulate (4), dass T alle positiven ganzen Zahlen enthält. ?

In einigen Fällen müssen wir die doppelte Induktion verwenden.

Satz 2.2. S(m, n) soll eine Aussage über zwei positive ganze Zahlen sein und annehmen, dass

S(1, 1) ist wahr,
für alle m und n, S(m, n) impliziert S(m+1, n) und S(m, n+1).

Dann gilt S(m, n) für alle Paare von positiven ganzen Zahlen.

Beweis. Sei T(n) die Aussage „S(m, n) ist wahr für alle ganzen Zahlen m“. Dann beweisen wir T(n) durch Induktion.

Für n = 1 wird T(1) zu „S(m, 1) ist für alle m wahr“. Dies kann durch Induktion an m nachgewiesen werden:

Für m = 1 ist S(m, 1) durch die Hypothese (1) wahr.

Wenn S(m, 1) wahr ist, dann ist S(m+1, 1) wahr durch die Hypothese (2).

Dann nehmen wir an, dass T(n), das zu „S(m, n) ist wahr für alle m“ wird. Durch die Hypothese (2) ist „S(m, n+1) für alle m“ wahr, also T(n+1).

Somit gilt T(n) für alle n, was das gewünschte Ergebnis war. ?

Eng verbunden mit der mathematischen Induktion ist eine Technik namens Rekursion. Wir können eine Funktion f definieren, indem wir f(1) definieren und f(n+1) in Bezug auf n und f(n) definieren. Der folgende Satz zeigt, dass diese Technik eine eindeutige Funktion auf die positiven ganzen Zahlen definiert.

Satz 2.3. Laß R ein beliebiger nicht leerer Satz sein. Lassen Sie F: R ⨯ Z + ⟶ R und lassen Sie A ein beliebiges Element von R sein. Dann gibt es eine und nur eine Funktion f : Z + ⟶ R so dass

f(1) = A
f(n+1) = F(f(n), n)

Beweis. Betrachten Sie alle Teilmengen S von Z +⨯ R, die die folgenden beiden Bedingungen erfüllen:

(1, A) ∈ S,
wenn (n, r) ∈ S dann (n+1, F(r, n)) ∈ S.

Lasst T den Schnittpunkt all dieser Teilmengen sein. Dann gehorcht T eindeutig auch den gleichen zwei Bedingungen, und T ist eine richtige Teilmenge von jeder anderen Menge, die den Bedingungen gehorcht.

Als nächstes beweisen wir durch Induktion, dass es für jede positive ganze Zahl n ein und nur ein r gibt, so dass (n, r) in T ist.

Für n = 1 entspricht dies der Aussage, dass (1, A) das einzige Paar in T mit dem ersten Element 1 ist. Nehmen wir zum Zwecke des Widerspruchs an, dass (1, B) in T für einige B in R anders als A ist. Dann gehorcht die Menge T – {(1, B)} beiden Bedingungen, aber T ist keine richtige Teilmenge davon.

Angenommen, die Hypothese ist wahr für n, und (n,r) ist das einzige Paar in T mit dem ersten Element gleich n. Dann (n+1, F(r,n)) ist auch in T. Nehmen wir zum Zwecke des Widerspruchs an, dass (n+1, C) in T für einige C in R außer F(r,n) ist. Dann gehorcht die Menge T – {(n+1, C)} beiden Bedingungen, aber T ist keine richtige Untermenge davon.

Für jede positive ganze Zahl n soll f(n) das Element von R sein, so dass (n, f(n)) zu T gehört. Dann ist es einfach zu zeigen, dass f die gewünschte Funktion ist.

Es ist einfach, durch Induktion zu beweisen, dass die Funktion f einzigartig ist. ?

Es gibt im Wesentlichen nur ein System von positiven ganzen Zahlen, wie das folgende Theorem zeigt.

Satz 2.4. Zwei beliebige Systeme, die den Peano-Postulaten gehorchen, sind isomorph, d.h. wenn X und Y zwei solche Systeme sind, dann gibt es eine Eins-zu-Eins-Korrespondenz f : X ⟶ Y so, dass f(1) = 1 und f(n+1) = f(n)+1.

Beweis. Nach dem vorherigen Satz gibt es eine Funktion f : X ⟶ Y, so dass

f(1) = 1
f(n+1) = f(n)+1

Die Funktion f ist die erforderliche Isomorphie, vorausgesetzt, sie ist eins zu eins und ihr Bereich ist ganz Y.

Wir zeigen zunächst, dass f eins zu eins ist, d.h. dass f(a) = f(b) bedeutet, dass a = b. Wir verwenden Induktion auf den gemeinsamen Wert n von f(a) und f(b).

Für n = 1 haben wir f(a) = f(b) = 1. Wenn a nicht gleich 1 ist, dann a = c+1 für eine ganze Zahl c, und damit f(a) = f(c+1) = f(c+1) = f(c)+1, was nicht gleich 1 ist, also a = 1. Ebenso ist b = 1.

Gehen Sie nun davon aus, dass f(a) = f(b) = n bedeutet, dass a = b und betrachten Sie f(c) = f(d) = n+1. Dann kann c nicht gleich 1 sein, also c = g+1 für eine ganze Zahl g. Daher f(c) = f(g+1) = f(g)+1 = n+1, also f(g) = n. Ebenso d = h+1 und f(h) = n. Durch induktive Hypothese, g = h. Daher c = g+1 = h+1 = h+1 = d.

Wir zeigen nun, dass der Bereich von f der gesamte Bereich von Y ist. Offensichtlich liegt 1 im Bereich, und wenn n im Bereich liegt, ist es auch n+1. Durch mathematische Induktion liegen alle Elemente von Y im Bereich. ?

3. Ergänzung

Die positiven Ganzzahlen haben auch eine Additionsoperation. Bisher haben wir nur ein einziges Beispiel für die Addition gesehen, n+1. Wir möchten, dass die Ergänzung mit diesem Beispiel übereinstimmt und die assoziativen und kommutativen Gesetze befolgt:

n+1 ist der Nachfolger von n
m+(n+p) = (m+n)+p (Addition ist assoziativ)
m+n = n+m (Addition ist kommutativ)

Satz 3.1. Es gibt genau eine Möglichkeit, die Addition auf Z + so zu definieren, dass die Addition assoziativ ist und n+1 der Nachfolger von n für jede positive ganze Zahl n ist.

Beweis. Lasst m eine beliebige positive ganze Zahl sein. Mit Theorem 2.3 gibt es eine Funktion fm, so dass:

fm(1) = m+1,
fm(n+1) = fm(n)+1 für jede positive ganze Zahl n.

Definiere dann m+n als fm(n). Es ist klar, dass für alle positiven ganzen Zahlen m und n,

m+1 ist der Nachfolger von m,
m+(n+1) = (m+n)+1 für jede positive ganze Zahl n.

Wir müssen nun zeigen, dass diese Operation assoziativ ist, auch wenn der letzte Operand nicht 1 ist, d.h. dass m+(n+p) = (m+n)+p für alle positiven ganzen Zahlen m, n und p.

Wir verwenden Induktion auf p. Für p=1 ist sie bereits nachgewiesen. Dann wenn m+(n+p) = (m+n)+p,

m+(n+(p+1)) = m+((n+p)+1) = (m+(n+p))+1 = ((m+n)+p)+1 = (m+n)+(p+1),

also gilt es auch für p+1.

Wenn ++ eine andere assoziative Operation ist, so dass m++1 = m+1, dann kann durch Induktion auf m leicht gezeigt werden, dass m++n = m+n für jede positive ganze Zahl n. Daher ist die Operation einzigartig. ?

Wir haben keine Ergänzung benötigt, um kommutativ zu sein, aber wir können beweisen, dass sie es ist.

Satz 3.2. Für beliebige positive ganze Zahlen m und n, m+n = n+m.

Beweis. Zuerst weisen wir den Sonderfall 1+n = n+1 durch Induktion auf n nach. Für n=1 ist es offensichtlich. Wenn 1+n = n+1, dann 1+(n+1) = (1+n)+1 = (n+1)+1.

Nun beweisen wir den allgemeinen Fall m+n = n+m durch Induktion auf m. Für m=1 reduziert er sich auf den Sonderfall. Wenn m+n = n+m dann (m+1)+n = m+(1+n) = m+(n+1) = (m+n)+1 = (n+m)+1 = (n+m)+1 = n+(m+1). ?

Wir haben noch keine Subtraktion, aber wir haben ein Kündigungsgesetz.

Satz 3.3. Wenn m+p = n+p für beliebige positive ganze Zahlen m, n und p, dann m = n.

Beweis. Wir verwenden Induktion auf p. Für p=1 ist die Aussage identisch mit Peano Postulat (3). Wenn m+(p+1) = n+(p+1) dann (m+p)+1 = (n+p)+1, also m+p = n+p durch das gleiche Postulat, und m=n durch die induktive Hypothese. ?

Die folgenden Theoreme mögen offensichtlich erscheinen, aber wir werden sie im nächsten Abschnitt benötigen.

Satz 3.4. Für alle positiven ganzen Zahlen m und n ist m+n nicht gleich m oder n.

Beweis. Wir verwenden Induktion auf n. Für n=1 ist m+1 nicht gleich 1, weil 1 nicht der Nachfolger einer positiven ganzen Zahl ist. Wenn m+n nicht gleich n ist, dann ist m+n+1 nicht gleich n+1, da verschiedene ganze Zahlen nicht den gleichen Nachfolger haben können.

Da die Addition kommutativ ist, ist m+n auch nicht gleich m. ?

Lehrsatz 3.5. Für alle positiven Ganzzahlen m und n gilt einer und nur einer der folgenden Punkte:

(1) m = n.
(2) Es gibt eine positive ganze Zahl p, so dass m+p = n.
(3) Es gibt eine positive ganze Zahl q, so dass m = n+q.

Beweis. Der Satz 3.4 zeigt, dass (1) mit (2) oder (3) nicht kompatibel ist. Außerdem, wenn (2) und (3) beide wahr wären, dann wäre m = m+p+q, was durch Theorem 3.4 unmöglich ist. Dies zeigt, dass nur eine der Bedingungen erfüllt sein kann.

Der andere Teil ist durch doppelte Induktion auf m und n. Wenn m=n=1 ist, dann hält (1). Nehmen wir nun an, dass eine der Bedingungen erfüllt ist.

Wenn m=n dann m und n+1 gehorchen (2) und m+1 und n gehorchen (3).

Wenn m+p = n, betrachten wir zwei Fälle.

Wenn p=1, dann m+1 = n, also m+1 und n gehorchen (1), und m und n+1 gehorchen (2), weil m+1+1+1 = n+1, also m+2 = n.

Wenn p nicht 1 ist, dann ist p = r+1 für einige r, also m+r+1 = n. Dann gehorchen m+1 und n (2) und ebenso m und n+1.

Der Nachweis für den Fall, dass m = n+q ähnlich ist. ?

4. Bestellung

Die Reihenfolge der positiven ganzen Zahlen (1, 2, 3, etc.) ist eine ihrer bekanntesten Eigenschaften, aber es ist ziemlich schwierig, sie genau zu untersuchen.

Theorem 4.1 Es gibt eine und einzige lineare Ordnung der positiven ganzen Zahlen, so dass n < n+1 für jede positive ganze Zahl n, und m < n wenn, und nur wenn, es eine positive ganze Zahl p gibt, so dass m+p = n.

Beweis. Definiere m < n, wenn es eine positive ganze Zahl p gibt, so dass m+p = n. Wenn n < s dann gibt es eine positive ganze Zahl t, so dass n + t = s. Dann (m+p) + t = s, also m + (p+t) = s und die Beziehung ist transitiv. Der Satz 3.5 zeigt, dass es sich um eine lineare Ordnung handelt.

Sei < jede lineare Ordnung so, dass n < n+1 für jedes n. Dann zeigen wir durch Induktion auf p, dass m < m+p für jede positive ganze Zahl p. Für p=1 ist es wahr durch Hypothese. Wenn m < m+p dann m+p < m+p+1 durch Hypothese, und m < m+p+1, weil die Operation transitiv ist. Wenn m < n durch die lineare Ordnung, dann durch Theorem 3,5 m = n oder es gibt ein p oder q, so dass m + p = n oder m = n + q. Die erste Möglichkeit wird ausgeschlossen, weil die Operation eine lineare Ordnung ist. Die dritte Möglichkeit impliziert, dass n < m, dies ebenfalls eliminiert wird. Daher m + p = n. ?

An dieser Stelle können wir beginnen, einige der offensichtlicheren Eigenschaften der positiven ganzen Zahlen zu verwenden.

5. Zählen

Zwei Sätze A und B haben die gleiche Anzahl von Elementen, wenn es eine Eins-zu-Eins-Korrespondenz zwischen ihnen gibt, d.h. eine Funktion f: A ⟶ B, so dass f(x) = f(y) wenn und nur wenn x = y. Es lässt sich leicht nachweisen, dass es sich um eine Äquivalenzbeziehung handelt.

Lassen Sie[1,n] die Menge aller positiven ganzen Zahlen kleiner oder gleich n darstellen, d.h. {m ∈ Z + | m ≤ n}. Wir sagen, dass diese Menge n Elemente hat. Jede Menge, die die gleiche Anzahl von Elementen wie[1,n] hat, hat auch n Elemente. Darüber hinaus ist das Kriterium dafür, eine Eins-zu-Eins-Korrespondenz zwischen[1,n] und einer Menge A, eine formale Beschreibung des täglichen Zählvorgangs.

Satz 5.1 Die Mengen[1,m] und[1,n] haben die gleiche Anzahl von Elementen, wenn und nur wenn m = n.

Beweis. Wenn m=n, dann sind[1,m] und[1,n] identisch. Wenn[1,1] und[1,n] die gleiche Anzahl von Elementen haben, muss jede Einzelkorrespondenz zwischen ihnen sowohl 1 in 1 als auch n (und andere Elemente von[1,n]) tragen. Dies ist unmöglich, es sei denn, n=1.

Nehmen wir nun an, dass[1,m+1] und[1,n] die gleiche Anzahl von Elementen haben und f eine persönliche Übereinstimmung zwischen ihnen ist. Das vorhergehende Argument zeigt, dass n=1 nicht möglich ist, so dass n-1 eine positive ganze Zahl ist.

Wenn f(m+1) = n, lassen Sie g f sein; ansonsten definieren Sie g durch

g(m+1) = n,
g(f -1(n)) = f(m+1), und
g(p) = f(p), für alle p ungleich m+1 oder f -1(n).

Dann ist g(m+1) = n, und g beschränkt auf[1,m] ist eine Eins-zu-Eins-Korrespondenz mit[1,n-1]. Durch induktive Hypothese m = n-1, was m+1 = n entspricht. ?

Satz 5.2 Wenn A und B disjunkte Mengen mit m- und n-Elementen sind, dann hat die Vereinigung C von A und B m+n-Elemente.

Beweis. Let f: A ⟶ [1,m] und g: B ⟶[1,n] sind Einzelkorrespondenzen. Dann definieren Sie h: C ⟶ [1, m+n] auf die naheliegende Weise:

h(x) = f(x), wenn x in A ist,
h(x) = m + g(x), wenn x in B ist.

Die Funktion h kann als Eins-zu-Eins-Funktion dargestellt werden. Wenn x ≠ y dann deutlich h(x) ≠ h(y) wenn x und y beide in A oder beide in B sind. Wenn x in A ist und y in B ist, dann können wir die im vorherigen Abschnitt festgelegten Ordnungseigenschaften verwenden, um das zu zeigen h(x) ≠ h(y).

Ebenso können wir zeigen, dass h auf[1, m+n] steht. Lass dich in[1, m+n] sein. Betrachten Sie dann die Fälle, in denen y<m, y = m und y > m. Wenn y < m oder y = m, dann h-1(y) = f-1(y). Wenn y > m dann y = m + p für einige p, und h-1(y) = g-1(p). ?

An dieser Stelle können wir eine eher einfache Erweiterung der mathematischen Induktion feststellen.

Theorem 5.3 Let S be a statement about a positive integer, and suppose that

S ist wahr für 1,
für alle n, wenn S für [1,n] wahr ist, dann ist es für n+1 wahr.

Dann gilt S für alle positiven Ganzzahlen.

Beweis. Wenden Sie den Satz 2.1 für die Aussage „S ist wahr für alle ganzen Zahlen zwischen 1 und n, einschließlich“ an. ? ?

Diese Variante der mathematischen Induktion ist in vielen Fällen bequemer, da die induktive Hypothese zum Nachweis einer Aussage S für n+1 etwas allgemeiner ist. Es kann davon ausgegangen werden, dass S für eine oder alle Ganzzahlen zwischen 1 und n einschließlich gilt.

6. Multiplikation

Die Multiplikation von positiven ganzen Zahlen ist eine weitere bekannte Operation. Informell kann die Multiplikation als wiederholte Addition definiert werden:

mn = m + m + m + m + m + m + ….. + m (n mal)

Dies deutet auf die folgenden formalen Eigenschaften hin:

m1 = m
m(n+1) = mn + mn + m

Es gibt nur einen Vorgang mit diesen Eigenschaften.

Satz 6.1. Es gibt genau eine Möglichkeit, die Multiplikation von positiven ganzen Zahlen so zu definieren, dass m1 = m und m(n+1) = mn + m.

Beweis. Lasst m eine beliebige positive ganze Zahl sein. Mit Theorem 2.3 gibt es eine einzigartige Funktion fm, so dass:

fm(1) = m
fm(n+1) = fm(n) + m für jede positive ganze Zahl n n

Wir definieren mn = fm(n). Dann folgen die gewünschten Eigenschaften direkt aus der Definition von f. ?

Die Multiplikation hat drei Eigenschaften, die einen Nachweis erfordern.

Satz 6.2. Die Multiplikation von positiven ganzen Zahlen hat folgende Eigenschaften:

m(n+p) = mn + mp (Multiplikation ist distributiv über Addition)
m(np) = (mn)p (Multiplikation ist assoziativ)
mn = nm (Multiplikation ist kommutativ)

Beweis. Wir beweisen die Verteilbarkeit durch Induktion auf p. Für p=1 folgt die Verteilbarkeit aus der Art und Weise, wie die Multiplikation definiert wurde. Nehmen wir nun an, dass m(n+p) = mn + mp. Dann

m(n+(p+1)) = m((n+p)+1) = m(n+p) + m = (mn+mp)+m = mn+(mp+m) = mn+m(p+1).

Wir beweisen Assoziativität durch Induktion auf p. Denn p=1 Assoziativität ist trivial. Nehmen wir nun an, m(np) = (mn)p. Dann

m(n(p+1)) = m(np + n) = m(np) + mn = (mn)p + mn = (mn)(p+1).

Wir beweisen die Kommutativität in zwei Schritten. Zunächst beweisen wir durch Induktion auf m, dass 1m = m1 = m1 = m. Für m=1 ist es trivial. Gehen Sie nun davon aus, dass 1m = m. Dann

1(m+1) = 1m + 1 = m+1.

Jetzt beweisen wir, dass mn = nm durch Induktion auf n. Für n=1 ist dies das Ergebnis gerade erst bewiesen. Gehen Sie nun von mn = nm aus. Dann

m(n+1) = mn + m = nm + m = m + nm = m + nm = m(1+n) = m(n+1).

Da die Multiplikation kommutativ ist, funktioniert die Verteilbarkeit in beide Richtungen:

m(n+p) = mn + mp,
(n+p)m = nm + pm.

Eine Eigenschaft der Multiplikation und Ordnung ist leicht nachzuweisen:

Satz 6.3. Wenn m, n, p und q positive ganze Zahlen sind und m > n und p > q, dann mp > nq.

Beweis. Per Definition gibt es positive ganze Zahlen u und v, so dass m = n+u und p = q+v. Nach den Verteilungs- und Assoziationsgesetzen:

mp = (n+u)(q+v) = (n+u)q + (n+u)v = nq + uq + nv + uv = nq + (uq + nv + uv).

Daher mp > nq per Definition. ? ?

7. Null

Das Konzept der Null kam ziemlich spät in der Geschichte der Mathematik. Die geometrischen Methoden der Antike erforderten es nicht.

Viele Eigenschaften der positiven ganzen Zahlen lassen sich leichter beschreiben, wenn wir eine zusätzliche ganze Zahl 0 definieren: Das erweiterte Zahlensystem wird als Menge nichtnegativer Ganzzahlen bezeichnet. Die grundlegende Eigenschaft von 0 ist, dass es sich um eine additive Identität handelt:

n + 0 = 0 + n = n = n, wobei n eine beliebige nichtnegative ganze Zahl ist.

Es ist leicht zu zeigen, dass die Addition von nichtnegativen ganzen Zahlen assoziativ und kommutativ ist, wenn die Addition von 0 auf diese Weise definiert wird. Es kann auch gezeigt werden, dass 0 die einzige additive Identität ist, d.h. dass m+n = n bedeutet, dass m=0.

Wir wollen die Multiplikation mit 0 definieren, damit das Verteilungsgesetz weiterhin wahr ist:

mn = m(n+0) = mn + m0.

Dies ist nur möglich, wenn m0 = 0, wenn die Multiplikation kommutativ sein soll, auch 0m = 0.

Es ist leicht zu zeigen, dass die assoziativen, distributiven und kommutativen Gesetze für die Addition und Multiplikation nichtnegativer Ganzzahlen gelten, wenn Addition und Multiplikation mit 0 auf diese Weise definiert sind.

Wir erweitern die Ordnungsbeziehung, indem wir 0 < n für jede positive ganze Zahl n definieren. Es ist einfach zu zeigen, dass die erweiterte Beziehung eine lineare Ordnung ist.

8. Negative Ganzzahlen und Subtraktion

Wir können das Zahlensystem weiter erweitern, indem wir eine negative ganze Zahl (-n) definieren, die jeder positiven ganzen Zahl n entspricht. Wir definieren die Addition einer positiven ganzen Zahl und ihrer und der entsprechenden negativen Zahl wie folgt:

n + (-n) = (-n) + n = 0.

Die positiven Ganzzahlen, Null und die negativen Ganzzahlen werden zusammen die Ganzzahlen genannt und werden in der Regel durch Z dargestellt.

Der Vollständigkeit halber definieren wir (-0) als 0; und wenn (-n) eine negative ganze Zahl ist, dann definieren wir (-(-n)) als n. Daher gilt die obige Identität für jede ganze Zahl n. Auch,

(-(-n) = n

für jede ganze Zahl n, ob positiv, negativ oder Null.

Für jede ganze Zahl n definieren wir den Absolutwert |n| von n wie folgt:

wenn n positiv oder Null ist, |n| = n,
wenn n eine negative ganze Zahl ist, dann |n| = (-n).

Wie bei 0 wollen wir andere Operationen mit negativen Zahlen definieren, damit die meisten Eigenschaften nichtnegativer Ganzzahlen weiterhin erhalten bleiben.

Die Addition einer negativen Zahl und 0 muss den Sonderstatus von 0 als additive Identität beibehalten:

(-n) + 0 = 0 + (-n) = (-n) = (-n).

Wenn zwei negative Zahlen hinzugefügt werden, stellen wir fest, dass, wenn die assoziativen und kommutativen Gesetze weiterhin gültig sind, dann

(-m) + (-n) + (m + n) = (-m) + m + (-n) + n = 0 + 0 = 0.

Daher müssen wir die Addition von zwei negativen Zahlen wie folgt definieren:

(-m) + (-n) = (-(m+n)).

Wenn eine positive Zahl m und eine negative Zahl (-n) addiert werden, gibt es drei Möglichkeiten:

Wenn m = n, dann m + (-n) = m + (-m) = 0.
Wenn m > n, dann m = n + p für einige positive p, und damit m + (-n) = n + p + (-n) = n + p + (-n) = n + (-n) + p = 0 + p = p.
Wenn m < n, dann n = m + p für etwas positives p, und damit m + (-n) = m + (-(m+p)) = m + (m + (-m) + (-p) = 0 + (-p) = (-p) = (-p).

Es kann gezeigt werden, dass die Addition von ganzen Zahlen, mit diesen Definitionen für die Addition von negativen ganzen Zahlen, immer noch assoziativ und kommutativ ist.

Überraschenderweise ist es einfacher, die Definition der Multiplikation auf negative ganze Zahlen auszudehnen.

Wenn m und n positive ganze Zahlen sind, dann, wenn das Verteilungsgesetz weiterhin für negative ganze Zahlen gilt.

m(-n) + mn = m((-n)+n) = m(0) = 0,

und wir müssen definieren.

m(-n) = (-(mn)).

Wenn die Multiplikation kommutativ ist, dann wird

(-n)m = (-(nm)).

In ähnlicher Weise,

(-m)(-n) + (-m)n = (-m)((-n)+n) = (-m)0 = 0,

und wir müssen definieren.

(-m)(-n) = (-((-m)n)) = mn.

Es kann gezeigt werden, dass die assoziativen, kommutativen und distributiven Gesetze gelten, wenn die Multiplikation auf diese Weise definiert wird.

Wir haben zuvor bewiesen, dass m < n, wenn es eine positive ganze Zahl p gibt, so dass m + p = n. Um diese Eigenschaft beizubehalten, wenn m oder n oder beides negativ sein kann, müssen wir Folgendes definieren

m < n, wenn m negativ ist und n nicht negativ ist.
m < n, wenn m und n beide negativ sind und (-n) < (-m)

Wir sind jetzt in der Lage, Subtraktion zu definieren:

m – n = m + (-n).

Wenn m und n beide positiv sind und m > n, dann stimmt dies mit der üblichen Definition der Subtraktion überein. In diesem Fall m = n+p für einige positive p, also m – n = n = n + p + (-n) = p + n + (-n) = p + n + (-n) = p + 0 = p.

Die Verwendung von negativen Zahlen vereinfacht die Berechnung in vielen Fällen, auch in Anwendungen, in denen negative Zahlen weder in den Daten noch in den Ergebnissen vorkommen. In einem System ohne negative Zahlen kann beispielsweise ein Ausdruck wie 5+6-7 als (5+6)-7 bewertet werden, aber nicht als 5+(6-7), da 6-7 nicht existieren würde.

9. Abteilung

Ganzzahlen können addiert, subtrahiert oder multipliziert werden. Eine Teilung ist nicht immer möglich, es sei denn, wir lassen Reste zu. Das folgende Theorem wird oft als Divisionsalgorithmus bezeichnet.

Satz 9.1. Wenn n (die Dividende) eine ganze Zahl und d (der Divisor) eine positive ganze Zahl ist, dann gibt es eindeutige ganze Zahlen q (der Quotient) und r (der Rest), so dass

n = qd + r und 0 ≤ r < d.

Beweis. Zuerst beweisen wir, dass q und r immer existieren.

Wenn n=0 dann q=r=0. wenn d=1 dann q=n und r=0. wenn n=1 und d>1 dann q=0 und r=1.

Für n>1 und d>1 verwenden wir Induktion auf n. Durch induktive Hypothese,

n = qd + r und 0 ≤ r < d.

Dann eindeutig

n+1 = qd + r + r + 1.

Wenn r+1 < d, ist dies das gewünschte Ergebnis für n+1. Andernfalls ist r+1 = d. Dann folgt

n+1 = qd + r+1 = qd + d = (q+1)d,

was das gewünschte Ergebnis für n+1 mit r=0 ist.

Wenn n < 0 dann -n positiv ist, so ist dies der Fall.

-n = qd + r und 0 ≤ r < d.

Daher

n = (-q)d – r – r

Wenn r=0 ist dies das gewünschte Ergebnis. Wenn r>0 dann

n = (-q-1)d + d – r,

und d-r im gewünschten Bereich liegt.

Nehmen wir nun an, dass q‘ und r‘ so sind, dass

n = q’d + r‘ und 0 ≤ r‘ < d.

Dann

0 = (q-q‘)d + (r-r‘) und -d < r-r‘ < d.

Gleichwertig,

(q-q‘)d = r‘-r und -d < r‘-r < d.

Aber wenn q-q‘ ≥ 1 dann (q-q‘)d ≥ d, und wenn q-q‘ ≤ -1 dann (q-q‘)d ≤ -d. Daher q-q‘ = 0 und r‘-r = 0. ?

Obwohl wir nicht immer teilen können, haben wir ein Kündigungsgesetz für die Multiplikation:

Satz 9.2. Wenn m, n und d ganze Zahlen sind, md = nd und d nicht Null ist, dann m=n.

Beweis. Wenn d positiv ist, dann gibt es durch den Teilungsalgorithmus eindeutige ganze Zahlen q und r, so dass

md = nd = qd + r, 0 ≤ r < d,

Wir stellen fest, dass q=m und r=0 oder q=n und r=0 zwei Paare sind, die diese Bedingungen erfüllen. Da die ganzen Zahlen eindeutig sind, m=n. ?

Wenn d ungleich Null ist und n = qd mit Rest Null, dann sagen wir, dass

n ist durch d teilbar, oder
d teilt n, oder
d ist ein Divisor von n, oder
d|n

und q = n/d.

Einige Ergebnisse über die Teilbarkeit sind offensichtlich:

Jede ungleich Null Ganzzahl teilt sich selbst.
Jede Ganzzahl ungleich Null teilt Null.
Die einzigen Teiler von 1 sind 1 und -1.
Die Ganzzahlen 1 und -1 teilen eine beliebige Ganzzahl.
Wenn m n und n m teilt, dann m = n oder m = -n.
Wenn m n und n p teilt, dann teilt m p.
Wenn m und n positive ganze Zahlen und m>n sind, dann teilt m nicht n.
Wenn m n und p teilt, dann teilt m n+p und n-p.
Wenn m n oder p teilt, dann teilt m np.

Bei unserer Untersuchung der Teilbarkeit betrachten wir nur positive ganze Zahlen; in den meisten Fällen ist die Erweiterung auf negative Zahlen trivial.

Lassen Sie m und n zwei positive ganze Zahlen sein. Wir sagen, dass g der größte gemeinsame Teiler von m und n ist, wenn

g teilt sowohl m als auch n, und
jede positive ganze Zahl, die sowohl m als auch n teilt, teilt auch g.

Der folgende Satz besagt nicht nur, dass zwei beliebige positive ganze Zahlen einen größten gemeinsamen Divisor haben, sondern schlägt auch eine praktische Methode zur Berechnung vor. Es wird der euklidische Algorithmus genannt.

Satz 9.3. Zwei beliebige positive ganze Zahlen m und n haben einen größten gemeinsamen Divisor g, und es gibt nichtnegative ganze Zahlen a und b, so dass

am – bn = g.

Beweis. Lassen Sie z = m+n-1. Wir verwenden Induktion auf z. Wenn z=1, dann eindeutig m=n=1, g=1, a=1 und b=0.

Wenn z > 1 keine Allgemeingültigkeit verloren geht, indem man davon ausgeht, dass m ≤ n. (Wenn m > n, können wir das gleiche Argument mit m und n vertauscht verwenden.) Durch Theorem 9.1 gibt es ganze Zahlen q und r, so dass

n = qm + r, 0 ≤ r < m.

Wenn r=0, dann a=1, b=0 und g=m, und es ist klar, dass g der größte gemeinsame Divisor von m und n ist.

Wenn r nicht Null ist, dann bemerken wir zuerst, dass jeder Teiler von m und n auch ein Teiler von r ist, und dass jeder Teiler von m und r auch ein Teiler von n ist. Daher ist der größte gemeinsame Teiler von m und r derselbe wie der größte gemeinsame Teiler von m und n.

Seit m≤n, r<n und m+n-1 < m+r-1. Daher können wir die induktive Hypothese auf m und r verwenden, um die ganzen Zahlen a‘, b‘ und g so zu erhalten:

a’m – b’r = g.

Dann ist es einfach zu zeigen, dass g und die folgenden Werte von a und b alle Anforderungen erfüllen:

a = a‘ + b’q, b = b‘.

Der größte gemeinsame Divisor von m und n wird normalerweise geschrieben (m,n) oder gcd(m,n).

10. Primzahlen

Eine Primzahl p ist eine ganze Zahl größer als 1, die keine positive ganze Zahl außer 1 und p teilbar ist.

Satz 10.1. Jede ganze Zahl größer als 1 ist entweder prime oder ein Produkt von primes.

Beweis. Wir verwenden Induktion. Offensichtlich gilt die Aussage für 1, wenn auch leer.

Wenn eine ganze Zahl größer als 1 prim ist, ist die Aussage eindeutig wahr. Wenn nicht, dann kann es in zwei kleinere ganze Zahlen zerlegt werden, von denen keine 1 ist, und durch induktive Hypothese ist jede von ihnen entweder eine Primzahl oder ein Produkt von Primzahlen. Daher ist die Zahl selbst ein Produkt von Primzahlen. ?

Wenn gcd(m,n) = 1 ist, dann gelten m und n als relativ primär.

Satz 10.2. Wenn eine Primzahl p das Produkt mn aus zwei positiven ganzen Zahlen teilt, dann teilt sie entweder m oder n (oder beide).

Beweis. Angenommen, p teilt weder m noch n. Da p prime ist, sind seine einzigen Teiler 1 und p. Da p m nicht teilt, muss der einzige gemeinsame Teiler von p und m 1 sein. Dann gibt es durch Theorem 9.3 ganze Zahlen a und b, so dass

ap – bm = 1.

Ebenso gibt es ganze Zahlen c und d, so dass

cp – dn = 1.

Multipliziert man diese beiden Gleichungen, erhält man

acp2 – adnp – cbmp + bdmn = 1.

Dann ist jeder Begriff auf der linken Seite durch p teilbar, aber das rechte Element ist nicht durch p teilbar. Das ist der gewünschte Widerspruch. ?

Folgerung 10.3. Wenn eine Primzahl das Produkt aus drei oder mehr positiven ganzen Zahlen teilt, muss sie mindestens eine von ihnen teilen.

Satz 10.4. Lassen Sie p1 p2 …. pm = q1 q2 …. qn, wobei alle Faktoren prime sind. Dann enthält m=n und das rechte Element die gleichen Faktoren wie das linke Element, die sich höchstens in der Reihenfolge unterscheiden.

Beweis. Wir verwenden Induktion auf m. Wenn m=1, dann muss n auch 1 sein, sonst wäre p1 ein Produkt von Primzahlen und könnte selbst nicht Primzahlen sein. Daher p1 = q1.

Wenn m>1, dann muss p1 durch die Folgerung 10.3 mindestens einen der Faktoren in q1 q2 teilen… qn. Da eine Primzahl keine andere Primzahl teilen kann, muss p1 gleich mindestens einem der Faktoren in q1 q2 sein…. qn.

Wir verwenden Theorem 9.2, um diese gemeinsame Primzahl von beiden Seiten zu erreichen. Dann verwenden wir die induktive Hypothese auf das, was bleibt. ?

Der folgende Satz folgt direkt aus den Theoremen 10.1 und 10.4. Es wird als der grundlegende Satz der Arithmetik bezeichnet.

Satz 10.5. Jede ganze Zahl größer als 1 kann in einer oder mehreren Primzahlen auf eine Weise berücksichtigt werden, die unabhängig von der Reihenfolge der Faktoren eindeutig ist.

10. Modulare Arithmetik

M soll eine positive ganze Zahl sein. Zwei ganze Zahlen m und n gelten als kongruent in Bezug auf den Modul M, wenn ihre Differenz m-n durch N teilbar ist. Manchmal wird dies mit „kongruentes Modul M“ abgekürzt, oder einfach „kongruent“, wenn der Modul verstanden wird. In Symbolen wird die Beziehung als m ≡ n (Modul M) oder m ≡ n ausgedrückt, wenn der Modul verstanden wird.

Es lässt sich leicht nachweisen, dass die Kongruenz in Bezug auf einen bestimmten Modul eine Äquivalenzbeziehung ist:

Es ist reflexiv: n ≡ n.
Es ist symmetrisch: m ≡ n impliziert, dass n ≡ m.
Es ist transitiv: m ≡ n und n ≡ p bedeuten, dass m ≡ p.

Die Kongruenz hat andere Eigenschaften mit der Gleichheit gemeinsam. Kongruente Ganzzahlen haben kongruente Summen, Differenzen und Produkte, d.h. wenn a ≡ b und c ≡ d dann a+c ≡ b+d, a-c ≡ b-d und ac ≡ bd. (a/c ist jedoch nicht unbedingt kongruent zu b/d, auch wenn die Quotienten existieren.)

Wir können dann das Additions- und Multiplikationsmodul M für die Menge {0, 1, 2, 2, …., M-1} definieren. Wenn m und n in dieser Menge sind, dann sind die modulare Summe und das Produkt von m und n die Reste, wenn m+n bzw. mn durch M geteilt werden. Die modulare Arithmetik dieser Art gehorcht den gleichen kommutativen, assoziativen und distributiven Gesetzen wie die reguläre Arithmetik. Die Bestellbeziehungen gelten nicht, aber Null behält ihren Status als additive Identität und jede ganze Zahl n hat ein negatives M-n. Das Symbol ZM wird verwendet, um die Menge {0, 1, 2, …., M-1} mit diesen Operationen darzustellen.

Da die Kongruenz für einen bestimmten Modul eine Äquivalenzrelation ist, gibt es Äquivalenzklassen, die oft als Restklassen modulo M bezeichnet werden. Der Divisionsalgorithmus zeigt, dass jede ganze Zahl genau einer von 0, 1, 2, . kongruent ist…., M-1 modulo M; nämlich der Rest, wenn er durch M geteilt wird. Diese Zahl wird manchmal als ihr Restmodul M bezeichnet. Die Äquivalenzklassen werden manchmal anstelle der Menge {0, 1, 2, …., M-1} als Zahlen in der modularen Arithmetik verwendet. Dieser Ansatz führt jedoch nicht zu wesentlich unterschiedlichen Ergebnissen.

Wenn der Modul M eine Primzahl ist, können wir auch durch eine beliebige Zahl ungleich Null teilen. Wenn n in {1, 2, …., M-1} ist, dann ist der größte gemeinsame Teiler von n und M 1, und es gibt ganze Zahlen a und b, so dass ein + bM = 1, also ein ≡ 1, und amn ≡ m für jede ganze Zahl m. Daher ist der Rest von am m/n.

Das folgende Theorem wird oft als Fermat’s Little Theorem bezeichnet (um es von dem berühmteren Fermat’s Last Theorem zu unterscheiden):

Satz 10.1. Lasse p eine Primzahl sein und lasse n eine beliebige ganze Zahl sein. Dann n p ≡ n (mod p).

Beweis. Es gibt mehrere Beweise für dieses Theorem. Die elementarste verwendet Induktion auf n und das Binomialtheorem.

Das Theorem ist offensichtlich für n = 0 und n = 1.

Für größere Werte von n, verwenden Sie das Binomialtheorem, um zu schreiben.

(n + 1) p = n p + p n p + p n p-1 + (p(p-1)/2!) n p-2 + (p(p-1)(p-2)/3!) n p-3 +…. + 1

Jeder Binomialkoeffizient außer dem ersten und letzten ist durch p teilbar. (Hier wird die Tatsache verwendet, dass p prime ist.) Daher (n + 1) p ≡ n p + 1. Darüber hinaus, n p ≡ n durch induktive Hypothese. Daher (n + 1) p ≡ n+1.

Dies beweist den Satz für alle nicht-negativen n. Für negative n, wenn p ≠ 2, n p = (-1) p (-n) p = (-1)(-n) = n.

Im Sonderfall, in dem p = 2 ist, behauptet das Theorem, dass n 2 und n beide gerade oder beide ungerade sind, was ziemlich offensichtlich ist. ?

Das Theorem wird manchmal in ähnlicher Form wiedergegeben:

Folgerung 10.2. Lasst p eine Primzahl sein, und lasst n eine beliebige ganze Zahl sein, die nicht durch p teilbar ist. Dann n p-1 ≡ 1 (mod p).

Zur Akkuschrauber Homepage