Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 18.12.2000

§9 Teilbarkeit im Bereich der ganzen Zahlen

Wir beschäftigen uns in diesem Paragraphen mit den grundlegenden Begriffen aus der elementaren Zahlentheorie. Dazu gehören Teiler, Vielfaches, größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches. Zur Berechnung des größten gemeinsamen Teilers behandeln wir den euklidischen Algorithmus. Wesentliches Hilfsmittel dafür ist die Division mit Rest.

Auf der Menge ZZ der ganzen Zahlen gibt es zwei Rechenoperationen (Verknüpfungen), und zwar die Addition und die Multiplikation, die allerdings unterschiedliche Eigenschaften haben. In beiden Fällen gelten die Kommutativität, Assoziativität und Distributivität. Für die Addition gibt es ein Nullelement, nämlich die Zahl 0, und für die Multiplikation gibt es ein Einselement (die Zahl 1).

Zu jeder Zahl aus ZZ gibt es die negative Zahl, jedoch gibt es zu z ∈ ZZ i.a. kein Inverses bzgl. der Multiplikation, das wieder in ZZ liegt. Man sagt, daß die ganzen Zahlen einen kommutativen Ring bilden, im Gegensatz etwa zu den reellen Zahlen, die einen Körper bilden. Der Ring ZZ ist außerdem nullteilerfrei , d.h. es gilt

∀ a, b ∈ ZZ : a · b = 0 ⟺ (a = 0 ∨ b = 0)

Wir stellen folgenden Unterschied bei den beiden Rechenoperationen + und · fest: Sind a und b beliebig vorgegebene ganze Zahlen, so hat von den beiden Gleichungen

(1) a + x = b (2) a · x = b

die erste immer eine Lösung in x_{0} ∈ ZZ , nämlich x_{0} = b − a ∈ ZZ, die zweite dagegen i.a. keine Lösung in ZZ, wie die folgenden Beispiele zeigen:

2 · x = 3 ist nicht in ZZ lösbar, da links immer eine gerade und rechts eine ungerade Zahl steht. Oder: Betrachtet man dies als Gleichung in Q, so wäre x_{0} = \frac{3}{2} ∉ ZZ die einzige Lösung.

0 · x = 1 ist in ZZ nicht lösbar, da links 0 und rechts 1 ≠ 0 steht. Allgemeiner: Die Gleichung 0 · x = b ist nur für b = 0 lösbar. In dem Falle hat sie dann aber jede ganze Zahl als Lösung.

2 · x = −8 ist lösbar in ZZ mit x_{0} = −4 ∈ ZZ

Die Forderung, daß (2) immer lösbar sein soll, falls a ≠ 0 ist,motiviert die Einführung der rationalen Zahlen, die dann einen Körper bilden. So weit werden wir nicht gehen, wir werden uns statt dessen mit den Fällen beschäftigen, in denen (2) lösbar ist. Dies führt auf den Teilbarkeitsbegriff.

\underline{(9.1) DEF:} a und b seien ganze Zahlen. a heißt ein Teiler von b (in Zeichen a| b), wenn es ein k ∈ ZZ gibt mit der Eigenschaft a · k = b . In dieser Situation sagt man auch, daß a die Zahl b teilt oder daß b ein (ganzzahliges) Vielfaches von a ist.

\underline{Beispiel:} 2|4 , − 3|9 , 2 |̸ 3 (teilt nicht) , 7|0 , 0|0 , 0 |̸ 1

Bei der Definition der Teilbarkeit wird die Division nicht benutzt. Nur im Falle a ≠ 0 bedeutet a| b , daß \frac{b}{a} eine ganze Zahl ist.

\underline{(9.2) BEM:} a) a| b ⟺ ∃ k ∈ ZZ : a · k = b a |̸ b ⟺ ∀ k ∈ ZZ : a · k ≠ b

b) Ist a ein Teiler von b und gilt ak = b, so ist auch k ein Teiler von b. k heißt ein zu a komplementärer Teiler von b. Er ist im Falle a ≠ 0 eindeutig bestimmt:

ak = b = ak′ ⟹ a(k − k′) = 0 ⟹^{a≠0} k − k′ = 0 ⟹ k = k′ .

c) ∀ a ∈ ZZ : a| 0 (a · 0 = 0)

d) ∀ b ∈ ZZ : 0| b ⟹ b = 0 (b = 0 · k = 0)

e) a| b ⟹ a|(−b) , (−a)| b , (−a)|(−b) . Hieraus ergibt sich: a| b ⟺ |a| | |b| .

Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 22.12.2000

In dem folgenden Satz sind die wichtigsten Eigenschaften der Teilbarkeitsbeziehung zusammengefaßt, die sich einfach auf Grundlage der Definition beweisen lassen:

\underline{(9.3) SATZ:} Für beliebige ganze Zahlen a, b, c, d gilt :

a) 1|a und a| a (Reflexivität)

b) a| b und b ≠ 0 ⟹ 1 ≤ |a| ≤ |b|

c) a| b und b| a ⟹ |a| = |b|

d) a|b und b|c ⟹ a| c (Transitivität)

e) a| b und c| d ⟹ ac | bd

f) a| b und a| c ⟹ a| (xb + yc) ∀ x, y ∈ ZZ .

\underline{(9.4) FOLG:} a) Jede ganze Zahl b ≠ 0 besitzt nur endlich viele Teiler.

b) 0 besitzt unendlich viele Teiler.

\underline{(9.5) LEMMA:} Sei n ∈ IN. Gilt dann mk = n mit k, m ∈ IN, so folgt m ≤ ⌊\sqrt{n}⌋ oder k ≤ ⌊\sqrt{n}⌋ .