Teilbarkeit
Die wichtigste Relation der elementaren Zahlentheorie ist die Teilbarkeit ohne Rest:
Definition (teilbar, Teiler, Vielfaches, d|a)
Ein a heißt teilbar (ohne Rest) durch ein d, in Zeichen d|a, falls gilt:
Es gibt ein k mit k d = a.
Die Zahl d heißt dann auch ein Teiler von a, und a heißt ein Vielfaches von d.
Wir stellen die elementaren Eigenschaften der Teilbarkeitsrelation in einem Satz zusammen.
Satz (Eigenschaften der Teilbarkeitsrelation)
Für alle a, b, c, d, …, n, m, … gilt:
(T1) a|a, 1|a, a|0, 0|a gdw a = 0, d|a gdw |d|||a|,
(T2) d|a und a|d gdw |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|(a b) und (n d)|(n a),
(T6) (ca)|(cb) und c ≠ 0 impliziert a|b,
(T7) d|a und d|b impliziert d|(na + mb).
Der Beweis dieser Eigenschaften sei dem Leser zur Übung überlassen.
Die Eigenschaft (T7) wird häufig verwendet, und wir betrachten sie deswegen noch etwas genauer. Hierzu definieren wir:
Definition (Linearkombination)
Ein c heißt eine Linearkombination von a und b, falls n und m existieren mit
c = n a + m b.
So sind zum Beispiel
13 = 2 · 4 + 1 · 5, 8 = 2 · 4 + 0 · 5, 0 = 0 · 4 + 0 · 5, − 1 = 1 · 4 + (− 1) · 5
Linearkombinationen der Zahlen 4 und 5. Die Eigenschaft (T7) besagt nun: Ist d ein Teiler von a und von b, so ist d auch ein Teiler jeder Linearkombination von a und b. Eine genaue Beschreibung der möglichen Linearkombinationen zweier Zahlen a und b wird sich im Laufe unserer Untersuchungen ergeben.
Wir betrachten nun die sog. Division mit Rest, die den Versuch beschreibt, eine Zahl a durch eine Zahl d zu teilen. Für d = 3 gilt z. B.
14 = 4 · d + 2, 18 = 6 · d + 0, − 5 = − 2 · d + 1, − 9 = − 3 · d + 0.
Für die Reste r = 2, 0, 1, 0 dieser Beispiele gilt 0 ≤ r < d. Wir zeigen allgemein:
Satz (Division mit Rest)
Für alle a und alle d ≥ 1 gibt es eindeutig bestimmte q und r mit:
a = qd + r, 0 ≤ r < d.
Das „q“ steht hierbei für „Quotient“ und das „r“ für „Rest“. Die Darstellung a = qd + r mit 0 ≤ r < d nennen wir auch die Division von a durch d mit Rest r.
Beweis
Wir nehmen zunächst an, dass a ≥ 0 gilt. Sei dann q ≥ 0 maximal mit qd ≤ a. Sei r = a − qd. Dann gilt a = qd + r, und nach Wahl von q ist 0 ≤ r < d.
Sei nun a < 0. Nach dem bereits Bewiesenen gibt es q′, r′ mit
− a = q′d + r′, 0 ≤ r′ < d.
Ist r′ = 0, so ist a = − q′d + 0, und wir sind fertig. Andernfalls sei q = − q′ − 1 und r = − r′ + d. Dann ist
a = (− q′)d − r′ = qd + d + r − d = qd + r, 0 ≤ r < d.
Damit ist die Existenzaussage bewiesen. Zum Beweis der Eindeutigkeit sei
a = q1d + r1 = q2d + r2 mit 0 ≤ r1 ≤ r2 < d.
Dann gilt r2 − r1 = (q1 − q2)d, also d|(r2 − r1). Dann ist aber r2 = r1, denn andernfalls wäre r2 − r1 ≠ 0 und damit ist d ≤ r2 − r1 < d, was nicht sein kann. Wegen r1 = r2 ist dann aber q1 d = q2 d, und wegen d ≠ 0 also q1 = q2. Damit ist auch die Eindeutigkeitsaussage des Satzes gezeigt.
Sind a = qd + r und b = q′d + r′ die Divisionen von a bzw. b durch d, so gilt
a − b = (q − q′)d + r − r′.
Wegen − d < r − r′ < d gilt also r = r′ genau dann, wenn d ein Teiler von a − b ist. Zwei Zahlen a und b haben also bei Division mit d genau dann den gleichen Rest, wenn ihre Differenz durch d teilbar ist. Wir definieren entsprechend:
Definition (kongruent modulo d, a ≡ b mod(d))
Sei d ≥ 1. Zwei Zahlen a und b heißen kongruent modulo d, in Zeichen a ≡ b mod(d), falls d|(a − b).
Diesem Kongruenzbegriff liegt folgende „geometrische“ Vorstellung der Kongruenz zugrunde: Wir können den Punkt a mit dem Punkt b zur Deckung bringen, indem wir a um ganzzahlige Vielfache von d entlang der Zahlengeraden verschieben.
Wir schreiben auch a ≡ b ≡ c ≡ … mod(d), falls die Zahlen a, b, c paarweise kongruent modulo d zueinander sind. Es gilt zum Beispiel:
1 ≡ 5 ≡ 9 ≡ … mod(4), 1 ≡ − 3 ≡ − 7 ≡ … mod(4).
Die Kongruenzrelation wird uns immer wieder begegnen und viele Beispiele für algebraische Strukturen zur Verfügung stellen.