Teiler und Vielfache
Die grundlegende Begriffsbildung dieses Kapitels ist:
Definition (Teilbarkeit, Teiler, Vielfaches)
Eine Zahl a heißt teilbar durch eine Zahl d, falls es ein k gibt mit a = k d. Die Zahl d heißt dann ein Teiler von a und a ein Vielfaches von d.
In Zeichen schreiben wir d | a [ gelesen: d teilt a ].
Beispiele
±2 | ±10, ±2 | ∓10, 0 | 0, 1 | 0, −1 | 0, nicht(3 | 10), nicht(0 | 1).
a | positive Teiler d von a | Anzahl τ(n) |
1 | 1 | 1 |
2 | 1, 2 | 2 |
3 | 1, 3 | 2 |
4 | 1, 2, 4 | 3 |
5 | 1, 5 | 2 |
6 | 1, 2, 3, 6 | 4 |
7 | 1, 7 | 2 |
8 | 1, 2, 4, 8 | 4 |
9 | 1, 3, 9 | 3 |
10 | 1, 2, 5, 10 | 4 |
11 | 1, 11 | 2 |
12 | 1, 2, 3, 4, 6, 12 | 6 |
13 | 1, 13 | 2 |
14 | 1, 2, 7, 14 | 4 |
15 | 1, 3, 5, 15 | 4 |
16 | 1, 2, 4, 8, 16 | 5 |
17 | 1, 17 | 2 |
18 | 1, 2, 3, 6, 9, 18 | 6 |
19 | 1, 19 | 2 |
20 | 1, 2, 4, 5, 10, 20 | 6 |
21 | 1, 3, 7, 21 | 4 |
22 | 1, 2, 11, 22 | 4 |
23 | 1, 23 | 2 |
24 | 1, 2, 3, 4, 6, 8, 12, 24 | 8 |
25 | 1, 5, 25 | 3 |
26 | 1, 2, 13, 26 | 4 |
27 | 1, 3, 9, 27 | 4 |
28 | 1, 2, 4, 7, 14, 28 | 6 |
29 | 1, 29 | 2 |
30 | 1, 2, 3, 5, 6, 10, 15, 30 | 8 |
Eine Visualisierung der Teilbarkeitsrelation: In der Graphik sind alle Paare (d, a) ∈ ℤ2 mit |d|, |a| ≤ 10 als Punkte eingezeichnet, für die d | a gilt. Für jedes d und a lassen sich anhand der Senkrechten durch (d, 0) alle Vielfachen von d und anhand der Waagrechten durch (0, a) alle Teiler von a ablesen.
Die Vergrößerung des Bereichs zeigt die Struktur der Teilbarkeitsrelation
Die wichtigsten elementaren Eigenschaften der Teilbarkeitsrelation auf den ganzen Zahlen versammelt der folgende Satz.
Satz (Eigenschaften der Teilbarkeit)
Für alle a, b, c, d, e, n, m gilt :
| (T1) | a | a, 1 | a, a | 0, |
| 0 | a genau dann, wenn a = 0, | |
| d | a genau dann, wenn |d| | |a|, | |
| (T2) | d | a und a | d genau dann, wenn |d| = |a|, |
| (T3) | d | a und a ≠ 0 impliziert |d| ≤ |a|, |
| (T4) | e | d und d | a impliziert e | a, |
| (T5) | d | a impliziert d | (ab) und (nd) | (na), |
| (T6) | (ca) | (cb) und c ≠ 0 impliziert a | b, |
| (T7) | d | a und d | b impliziert d | (na + mb). |
Der Beweis kann dem Leser zur Übung überlassen bleiben.
Die letzte Eigenschaft ist in Anwendungen besonders wichtig. Wir definieren hierzu:
Definition (Linearkombination)
Eine Zahl c heißt eine Linearkombination (in ℤ) von a und b, falls n, m existieren mit c = n a + mb.
Wir weisen nochmal darauf hin, dass n und m nach unserer Vereinbarung auch negativ sein können. In Linearkombinationen sind ausdrücklich auch negative Koeffizienten n und m zugelassen.
Die Eigenschaft (T7) besagt nun einfach: Ein Teiler zweier Zahlen ist auch ein Teiler jeder Linearkombination der beiden Zahlen.
Beispiele
13 = 2 · 4 + 1 · 5, 12 = 3 · 4 + 0 · 5,
0 = 0 · 4 + 0 · 5, − 1 = 1 · 4 − 1 · 5 = 1 · 4 + (−1) · 5.
Ein grundlegendes Ergebnis ist:
Satz (Division mit Rest)
Seien a, d ganze Zahlen mit d ≥ 1. Dann gibt es eindeutige q und r mit
a = q d + r, 0 ≤ r < d.
Weiter gilt r = 0 genau dann, wenn d | a.
Beweis
zur Existenz:
Sei q die größte ganze Zahl mit qd ≤ a (bestmögliche Annäherung von links an a mit Schrittweite d). Weiter sei r = a − qd. Dann gilt r ≥ 0 und
a = qd + a − qd = qd + r.
Nach maximaler Wahl von q ist (q + 1)d > a, sodass d > a − qd = r.
Damit sind q und r wie gewünscht.
zur Eindeutigkeit:
Seien q1, q2, r1, r2 ganze Zahlen mit
a = q1d + r1 = q2d + r2 mit 0 ≤ r1 ≤ r2 < d.
Dann gilt
r2 − r1 = (q1 − q2)d,
sodass r2 − r1 ein Vielfaches von d ist. Wegen 0 ≤ r1 ≤ r2 < d gilt aber 0 ≤ r2 − r1 ≤ d − 1. Damit ist notwendig r2 − r1 = 0, da die 0 das einzige Vielfache von d im Intervall von 0 bis d − 1 ist. Folglich ist r1 = r2. Aus
0 = r2 − r1 = (q1 − q2)d
ergibt sich nun wegen d ≠ 0, dass q1 = q2.
Definition (Quotient, Rest)
Gilt a = q d + r mit 0 ≤ r < d, so heißt q der Quotient und r der Rest der Division von a durch d.
Beispiele
10 = 3 · 3 + 1, 10 = 2 · 5 + 0, 10 = 0 · 18 + 10,
4 = 0 · 5 + 4, −4 = (−1) · 5 + 1, 23 = 4 · 5 + 3, −23 = (−5) · 5 + 2.
Der Rest der Division durch 5 dargestellt als Funktion von ℤ nach { 0, …, 4 }