§ 3. Teilbarkeit in �

\underline{(3.1) DEF:} a und b seien ganze Zahlen. Dann heißt a ein Teiler von b (in Zeichen: a | b) , wenn es eine ganze Zahl k ∈ ℤ gibt mit der Eigenschaft

a · k = b .

In diesem Fall sagt man auch, daß a die Zahl b teilt oder daß b ein (ganzzahliges) Vielfaches von a ist. a |̸ b bedeutet, daß a kein Teiler von b ist.

\underline{(3.2) BEM:} a) Seien a, b ∈ ℤ. Gilt a | b und ist \underline{b ≠ 0} , so gibt es \underline{genau} ein k ∈ ℤ mit a · k = b. k heißt dann der zu a komplementäre Teiler von b.

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

c) Für a ∈ ℤ und n ∈ ℕ gilt: n | a ⟺ a mod n = 0 .

\underline{(3.3) SATZ:} Eigenschaften der Teilbarkeit a, b, c seien ganze Zahlen. Dann gilt:

a) 1 | a , − 1 | a , a | a , − a | a für alle a ∈ ℤ.

b) a | 0 für alle a ∈ ℤ, insbesondere 0 | 0 .

c) 0 | b ⟺ b = 0

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

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

f) a | b und b | a ⟹ | a | = | b |.

g) a | b und a | c ⟹ a | (xb + yc) für alle x, y ∈ ℤ

h) a | b ⟺ | a | | | b | .

\underline{(3.4) BEM:} a) Nach (3.3) ist die Teilbarkeitsrelation | eine reflexive und transitive Relation auf ℤ. Man nennt daher (ℤ, |) auch eine halbgeordnete Menge . Die Einschränkung von | auf die Mengen ℕ_{0} und ℕ ist wegen (3.3f) auch antisymmetrisch, d.h. | ist eine Ordnungsrelation auf ℕ_{0} und auf ℕ. Die Teilbarkeitsrelation ist nicht linear (2 |̸ 3 und 3 |̸ 2) .

b) Jede ganze Zahl \underline{b ≠ 0} besitzt nur \underline{endlich} viele Teiler. Die Anzahl der Teiler von b ist ≤ 2 · | b |.

c) 0 ist die \underline{einzige} ganze Zahl, die unendlich viele Teiler besitzt.

\underline{(3.5) DEF:} Für b ∈ ℤ bezeichne

T (b) := { a | a ∈ ℤ , a | b } ⊆ ℤ

die Menge aller (ganzzahligen) Teiler von b, die sog. Teilermenge von b, und

T^{+}(b) := { n | n ∈ ℕ_{0} , n | b } ⊆ ℕ_{0}

die Menge aller nichtnegativen Teiler von b.

\underline{(3.6) SATZ:} Seien k, l, n ∈ ℕ und gelte n = k · l. Dann folgt k ≤ ⌊\sqrt{n}⌋ oder l ≤ ⌊\sqrt{n}⌋.

(3.7) Verfahren zur Bestimmung aller (positiven) Teiler einer ganzen Zahl b ≠ 0 :

(1) Bestimme m := ⌊\sqrt{| b |} ⌋

(2) Teste der Reihe nach, ob die Zahlen 1, 2, 3, …, m Teiler von | b | sind oder nicht. Berechne zu jedem gefundenen Teiler von | b | den dazu komplementären Teiler von | b |. Auf diese Art erhält man \underline{alle} positiven Teiler von b.

(3) Nimmt man zu jedem positiven Teiler a von b auch noch die negative Zahl −a hinzu, so erhält man alle ganzzahligen Teiler von b.

\underline{(3.8) DEF:} Die Anzahl aller positiven Teiler einer natürlichen Zahl n ∈ ℕ wird mit τ (n) bezeichnet. Die Funktion τ : ℕ ⟶ ℕ , n ⟼ τ(n) , heißt Teileranzahlfunktion .

\underline{(3.9) BEM:} a) τ(n) = | T^{+}(n) | b) Nach (3.4) gilt 1 ≤ τ(n) ≤ n

c)  n  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
τ(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2
ungerade ↑  ↑  ↑  ↑

\underline{(3.10) SATZ:} Sei n ∈ ℕ. Genau dann ist n eine Quadratzahl, wenn τ(n) ungerade ist.

\underline{(3.11) DEF:} Die Summe aller positiven Teiler einer natürlichen Zahl n ∈ ℕ wird mit σ(n) bezeichnet. Die Funktion σ : ℕ ⟶ ℕ , n ⟼ σ(n) , heißt Teilersummenfunktion .

\underline{(3.12) BEM:} a) Für n ∈ ℕ gilt: σ(n) = ∑_{t∈T^{+}(n)} t.

Chr.Nelius : Zahlentheorie (SS 2007) 8

b) σ(1) = 1 < 2 · 1
σ(2) = 1 + 2 = 3  < 2 · 2
σ(3) = 1 + 3 = 4  < 2 · 3
σ(4) = 1 + 2 + 4 = 7  < 2 · 4
σ(5) = 1 + 5 = 6  < 2 · 5
σ(6) = 1 + 2 + 3 + 6 = 12  =2 · 6
σ(7) = 1 + 7 = 8  < 2 · 7
σ(8) = 1 + 2 + 4 + 8 = 15  < 2 · 8
σ(9) = 1 + 3 + 9 = 13  < 2 · 9
σ(10) = 1 + 2 + 5 + 10 = 18  < 2 · 10
σ(11) = 1 + 11 = 12  < 2 · 11
σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 >2 · 12
σ(13) = 1 + 13 = 14  < 2 · 13
⋮
σ(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56 =2 · 28

\underline{(3.13) DEF:} Eine natürliche Zahl n ∈ ℕ heißt vollkommen , wenn σ(n) = 2 · n gilt. \underline{Beispiele:} 6 und 28 sind vollkommene Zahlen. Die Teilbarkeit zweier ganzer Zahlen läßt sich mit Hilfe der Teilermengen feststellen: \underline{(3.14) SATZ:} Für a, b ∈ ℤ sind folgende Aussagen äquivalent:

a) a | b b) T^{+}(a) ⊆ T^{+}(b) c) T (a) ⊆ T (b) . Analog betrachten wir die Menge der Vielfachen \underline{(3.15) DEF:} Für a ∈ ℤ bezeichne

V (a) := { b | b ∈ ℤ , a | b } ⊆ ℤ

die Menge aller (ganzzahligen) Vielfachen von a, die sog. Vielfachenmenge von a, und

V^{+}(a) := { n | n ∈ ℕ_{0} , a | n } ⊆ ℕ_{0}

die Menge aller nichtnegativen Vielfachen von a. \underline{(3.16) BEM:} a) Es ist V (a) = ℤa ein Ideal in ℤ.

b) Für jedes a ∈ ℤ , \underline{a ≠ 0} sind V (a) und V^{+}(a) unendliche Mengen.

c) 0 ist die einzige ganze Zahl, die nur endlich viele Vielfache besitzt (V (0) = {0} = ℤ0). \underline{(3.17) SATZ:} Für a, b ∈ ℤ sind folgende Aussagen äquivalent:

a) a | b  b) V^{+}(b) ⊆ V^{+}(a)  c) V (b) ⊆ V (a) .