______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.1. Elementare Teilbarkeitslehre

______________________________________________________________________________

Im Folgenden bezeichnen kleine lateinische Buchstaben stets ganze Zahlen. Wir sagen d teilt n oder d ist ein Teiler von n, wenn ein b existiert, so dass n = bd; in Zeichen: d | n. Natürlich gilt in diesem Fall auch b | n; dabei heißt b der zu d komplementäre Teiler. Ansonsten ist d kein Teiler von n, was wir mit d ∤ n notieren. Dieses Prinzip der Teilbarkeit begegnet uns auch im Alltag.

Beispielsweise gelten

2 | 100, 11 | 165, − 13 | 169, 5 ∤ 21.

Es bestehen die folgenden Rechenregeln zur Teilbarkeit:
  1. 1 | n und n | n und d | 0;
  2. 0 | d ⇒ d = 0; d | 1 ⇒ d = ±1;
  3. d | n, n | m ⇒ d | m;
  4. d | a, d | b ⇒ d | (ax + by) für alle x,y ∈ ℤ;
  5. bd | bn, b ≠ 0 ⇒ d | n (Kürzungsregel);
  6. d | n, n ≠ 0 ⇒|d|≤|n|;
  7. d | n, n | d ⇒ d = ±n.

Hierbei ist der Betrag |x| definiert als das Maximum von x und −x. Von diesen vielen Regeln verifizieren wir hier nur (4.): Nach Voraussetzung gelten a = md und b = nd mit gewissen m, n. Dann gilt für beliebige x,y ∈ ℤ zunächst ax + by = mdx + ndy = (mx + ny)d und damit d | (ax + by).

Aufgabe 1. Beweisen Sie die restlichen Rechenregeln zur Teilbarkeit.

Aus Rechenregel (4.) folgt u.a., dass eine ganze Zahl ≠ 0 nur endlich viele Teiler besitzt. Damit besitzen a,b ∈ ℤ, nicht beide gleich Null, einen größten gemeinsamen Teiler ggT(a,b) ∈ ℕ, für den also gilt

  • ggT(a,b) | a und ggT(a,b) | b;
  • wenn d | a und d | b, dann d | ggT(a,b).

Streng genommen ist die Existenz einer solchen Zahl ggT(a,b) hier zu zeigen. Hierzu kann man z.B. wieder mit Hilfe der Wohlordnung argumentieren; die Menge der Teiler d von a und b ist nicht-leer (da 1 | a und 1 | b). Ferner setzen wir ggT(0, 0) = 0. Gilt ggT(a,b) = 1, so nennen wir a und b teilerfremd.

Wie so oft starten wir mit einer simplen Tatsache, die sich jedoch als sehr wichtig erweisen wird und deshalb auch einen Namen trägt:

Satz (Division mit Rest).

Zu a,b ∈ ℤ mit b ≠ 0 existieren eindeutig bestimmte ganze Zahlen q,r, so dass

a = bq + r mit 0 ≤ r < |b|.


Beweis. Mit dem Prinzip der Wohlordnung besitzt

N = {a − bq : q ∈ ℤ } ∩ ℕ ∪ {0}

ein kleinstes Element r. Falls b ∤ a gilt 1 ≤ r < |b|; andernfalls ist r = 0 und in jedem Fall sind q,r ∈ ℤ offensichtlich eindeutig. qed.

Die Aussage des Satzes wird kurz mit ’Division mit Rest’ bezeichnet, weil in

a/b = q + r/b

für natürliche Zahlen b die Zahl q der eindeutig bestimmte Ganzteil von a/b ist, d.h. die größte ganze Zahl ≤ a/b; für den Rest gilt dabei 0 ≤ r/b < 1. Der Beweis des Satzes ist konstruktiv: Sind etwa a = 33 und b = 5 gegeben, so sind die ganzen Zahlen a − bq = 33 − 5q gegeben durch

..., − 2 = 33 − 5 ⋅ 7, 3 = 33 − 5 ⋅ 6, 8 = 33 − 5 ⋅ 5, 13 = 33 − 5 ⋅ 4, ...,

also N = {3, 8, 13,…} (denn die negativen a − bq gehören ja nicht zu N). Es ist hierbei offensichtlich
a − bq < 0 ⇐⇒ q > a/b falls b > 0
(bzw. q <a/b falls b < 0), so dass also letztlich nur wenige Werte für q mit eben 0 ≤ r = a − bq < |b| in Frage kommen. Oder noch einfacher: Mit Hilfe unserer vorangegangenen Bermerkung ist q als die eindeutig bestimmte größte ganze Zahl ≤ a/b zu nehmen; der Rest r ergibt sich dann unmittelbar.
Im Beispiel:
33/5= 6 + 3/5 .

Hier nun eine erste wichtige Konsequenz:

Korollar.

Für a,b ∈ ℤ mit b ≠ 0 bezeichne d = ggT(a,b). Dann gilt

d ℤ := {dk : k ∈ ℤ} = {ax + by : x,y ∈ ℤ}.

Der größte gemeinsame Teiler zweier ganzer Zahlen a,b lässt sich also als Linearkombination ax + by von a und b schreiben!

Beweis. Wir nehmen an, dass a ≠ 0 ist (ansonsten ist die zu beweisende Aussage trivial). Wir definieren

Z := {ax + by : x,y ∈ ℤ } ⊂ ℤ

und nennen m die kleinste natürliche Zahl in Z, also m := min{n ∈ ℕ ∩ Z} (existent auf Grund der Wohlordnung). Wir schreiben stets min{x : x ∈ M} für das kleinste Element einer Menge M (wenn es denn existiert). Nach Rechenregel (4.) gilt d | z für jedes z ∈ Z, also Z ⊂ dℤ und d | m. Nun ist mit a,qm ∈ Z auch a − qm ∈ Z (wie man sofort nachrechnet). Division mit Rest von a durch m (statt b im vorherigen Satz) liefert den Rest 0 da m ∈ ℕ minimal in Z ist. Also gilt m | a und analog m | b (mit demselben Argument für b statt a auf Grund der Symmetrie). Also m ≤ d = ggT(a,b). Zusammen mit d | m folgt d = m (nach (7.)) und dℤ⊂ Z. Also ergibt sich insgesamt Z = dℤ. qed.

Einige Rechenregeln für den größten gemeinsamen Teiler:

  1. ggT(a,b) = ggT(b,a);
  2. ggT(a, ggT(b,c)) = ggT(ggT(a,b),c);
  3. ggT(ac,bc) = |c| ggT(a,b).

Das kleinste gemeinsame Vielfache zweier ganzer Zahlen a,b ist definiert als das Minimum aller m ∈ ℕ für die a | m und b | m gilt; in Zeichen kgV[a,b].

Aufgabe 2. Zeigen Sie für beliebige a,b ∈ ℤ die Formel

ab = ggT (a,b) ⋅ kgV [a,b].

Den größten gemeinsamen Teiler zweier ganzer Zahlen berechnet man am einfachsten mit dem so genannten euklidischen Algorithmus. Dieses Verfahren entspricht einer sukzessiven Division mit Rest (siehe obigen Satz).

Satz (Euklidischer Algorithmus).

Zu gegebenen natürlichen Zahlen a und b mit a > b seien r−1 := a,r0 := b und

a = q1b + r1,

b = q2 r1 + r2,

...

rj-2 = qj rj-1 + rj,

...

rn-2 = qn rm-1 + rn,

rn-1 = qn+1 rn

mit jeweils qj,rj ∈ ℤ und 0 ≤ rj< rj−1. Dann gilt für den letzten nicht verschwindenden Rest rn = ggT(a,b).

 

Beweis. Die Reste rj sind nicht-negative ganze Zahlen, die in jedem Schritt kleiner werden: 0 ≤ rj < rj−1. Also terminiert der Algorithmus (nach höchstens b Schritten). Durchläuft man das Gleichungssystem von unten nach oben, so zeigt sich

rn | rn-1 ⇒ rn|rn-2 ⇒ ... ⇒ rn | r0 = b ⇒ rn | r-1 = a.

Damit ist rn ein gemeinsamer Teiler von a und b. Für jeden gemeinsamen Teiler d von a und b ergibt sich beim Durchlauf des Gleichungssystems von oben nach unten sukzessive

d | a = r-1, d | b = r0 ⇒ d | r1 ⇒ ... ⇒ d | rn-1 ⇒ d | rn.

Also ist rn der größte gemeinsame Teiler von a und b. qed.


Beispiel des Euklidischen Algorithmus und Spiel zum Euklidischen Algorithmus.
Den größten gemeinsamen Teiler bzw. das kleinste gemeinsame Vielfache von mehr als zwei ganzen Zahlen erklärt man induktiv;

ggT (a,b,c) = ggT (a,ggT (b,c)).

Zahlen a1,…,am heißen teilerfremd, wenn ggT(a1,…,am) = 1 gilt; sie heißen paarweise teilerfremd, wenn ggT(ai,aj) = 1 für alle 1 ≤ i,j ≤ m mit i≠j besteht. Letzteres impliziert ihre Teilerfremdheit, die Umkehrung gilt jedoch nicht:

6 = 2 ⋅ 3, 10 = 2 ⋅ 5, 15 = 3 ⋅ 5.