Mathematische Grundlagen
Teilbarkeit, Kongruenz modulo n
Teilbarkeit
Definition: Seien a, d ∈ ℤ zwei ganze Zahlen. Die Zahl d teilt die Zahl a oder a ist durch d teilbar oder d ist Teiler von a, in Zeichen d | a, wenn a als ganzzahliges Vielfaches von d dargestellt werden kann:
d | a ⇔ ∃ k ∈ ℤ : k · d = a.
Beispiel: Die Zahl 3 teilt die Zahl 12, denn es gilt 4·3 = 12. Die Zahl 12 ist also durch 3 teilbar. Gleichermaßen teilt 3 die Zahlen 15, -12, 3 und auch 0.
Jede Zahl ist durch 1 teilbar. Jede Zahl ist durch sich selbst teilbar. Die 0 ist durch jede Zahl teilbar, auch durch 0. Außer der 0 ist keine Zahl durch 0 teilbar. Ist eine Zahl durch d teilbar, dann auch durch -d.
Satz: Die Relation | ("teilt") in ℤ ist transitiv, d.h. für alle a, b, c ∈ ℤ gilt
a | b ∧ b | c ⇒ a | c.
Definition: Die Teiler 1, -1, a und -a sind die trivialen Teiler von a. Die nichttrivialen positiven Teiler von a werden auch Faktoren von a genannt.
Beispiel: Die Zahl 20 hat die Faktoren 2, 4, 5 und 10. Die Zahl 7 hat keine Faktoren, sondern nur die trivialen Teiler ±1 und ±7.
Primzahlen
Definition: Eine Zahl a ∈ ℕ, a > 1 heißt Primzahl, wenn sie nur triviale Teiler, d.h. keine Faktoren hat. Anderenfalls heißt sie zusammengesetzt.
Die 1 spielt eine Sonderrolle und ist weder Primzahl noch zusammengesetzt. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Größter gemeinsamer Teiler
Definition: Seien a, b ∈ ℤ. Eine Zahl d ∈ ℤ ist ein gemeinsamer Teiler von a und b, wenn
d | a und d | b.
Die 1 ist stets gemeinsamer Teiler von beliebigen ganzen Zahlen.
Definition: Seien a, b ∈ ℤ. Eine Zahl g ∈ ℤ heißt größter gemeinsamer Teiler von a und b, wenn für alle d ∈ ℤ gilt
d | a ∧ d | b ⇔ d | g,
d.h. alle gemeinsamen Teiler von a und b sind auch Teiler von g, und alle Teiler von g sind auch gemeinsame Teiler von a und b.1)
In ℤ ist der größte gemeinsame Teiler von zwei Zahlen bis auf das Vorzeichen eindeutig bestimmt. Eigentlich kann man deshalb nicht von dem größten gemeinsamen Teiler sprechen, denn mit g ist auch stets -g größter gemeinsamer Teiler. Eindeutigkeit wird erreicht, indem der nichtnegative größte gemeinsame Teiler als der größte gemeinsame Teiler angesehen wird.
Definition: Die Funktion ggt : ℤ × ℤ → ℕ0 ist definiert durch
ggt(a, b) = g,
wobei g größter nichtnegativer gemeinsamer Teiler von a und b ist.
Beispiel: Es gilt
ggt(12, 30) = 6
ggt(24, 8) = 8
ggt(14, 25) = 1
ggt(17, 32) = 1
Allgemein gilt für alle a ∈ ℤ:
ggt(0, a) = |a|
Insbesondere gilt
ggt(0, 0) = 0
Definition: Zwei Zahlen a, b ∈ ℤ werden als teilerfremd bezeichnet, wenn ggt(a, b) = 1 ist.
Der größte gemeinsame Teiler von zwei nichtnegativen ganzen Zahlen lässt sich effizient mit dem euklidischen Algorithmus berechnen.
Kongruenz modulo n
Definition: Sei n ∈ ℕ. Die Relation kongruent modulo n auf der Menge der ganzen Zahlen ℤ ist wie folgt definiert:
a ≡ b (mod n) ⇔ n | a – b
für alle a, b ∈ ℤ.
Zwei Zahlen sind also kongruent (modulo n), wenn ihre Differenz durch n teilbar ist.
Beispiel: Es gilt beispielsweise:
17 ≡ 2 (mod 5), 2 ≡ 17 (mod 5), 6 ≡ 0 (mod 2), -6 ≡ 8 (mod 2)
Dagegen gilt nicht: 17 ≡ -17 (mod 5), denn 17 – (-17) = 34, und 34 ist nicht durch 5 teilbar.
Satz: Die Relation ≡ (mod n) ist eine Kongruenzrelation, d.h. eine verknüpfungstreue Äquivalenzrelation, denn es gilt für alle a, b, c, d ∈ ℤ
a ≡ b (mod n) ∧ c ≡ d (mod n) ⇒ a + c ≡ b + d (mod n) sowie
a ≡ b (mod n) ∧ c ≡ d (mod n) ⇒ a · c ≡ b · d (mod n)
Definition: Sei a ∈ ℤ, n ∈ ℕ. Die Operation mod ist wie folgt definiert:
a mod n = r ⇔ a ≡ r (mod n) ∧ 0 ≤ r < n
Es ist zu unterscheiden zwischen der Operation mod n und der Relation ≡ (mod n). Wenn a mod n = b ist, so ist zwar stets a ≡ b (mod n), umgekehrt jedoch nicht, denn z.B. ist 8 ≡ 6 (mod 2), aber 8 mod 2 ≠ 6.
Satz: Zwei ganze Zahlen a und b sind kongruent modulo n, wenn sie bei ganzzahliger Division durch n denselben Rest ergeben:
a ≡ b (mod n) ⇔ a mod n = b mod n
Bemerkung: Die Relation ≡ (mod n) ist eine Äquivalenzrelation. Eine Äquivalenzrelation bewirkt stets eine Klasseneinteilung der Grundmenge in Klassen äquivalenter Elemente. Die Äquivalenzklassen der Relation ≡ (mod n) enthalten jeweils diejenigen Zahlen, die bei Division durch n denselben Rest ergeben, sie heißen deshalb Restklassen. Die kleinste nichtnegative Zahl in jeder Restklasse ist Repräsentant der Restklasse.
Die Relation ≡ (mod n) teilt ℤ in n Restklassen mit den Repräsentanten 0, 1, 2, ..., n-1 ein.
Beispiel: Es sei n = 2. Die Relation ≡ (mod 2) teilt ℤ in zwei Restklassen ein: die geraden und die ungeraden Zahlen. Repräsentant der geraden Zahlen ist die 0, Repräsentant der ungeraden Zahlen die 1.
Die Menge ℤn
Die Menge {0, 1, 2, ..., n-1} der Repräsentanten der Restklassen modulo n bildet die Menge ℤn.
Definition: Sei n ∈ ℕ. Die Menge ℤn ist definiert als
ℤn = {0, 1, 2, ..., n-1}
Definition: Sei n ∈ ℕ. Auf der Menge ℤn werden Verknüpfungen +n (Addition modulo n) und ·n (Multiplikation modulo n) wie folgt definiert:
a +n b = (a + b) mod n
a ·n b = (a · b) mod n
Wenn aus dem Zusammenhang klar ist, dass modulo n gerechnet wird, schreiben wir einfach + und · statt +n und ·n.
Beispiel: Sei n = 5. Es gilt
ℤ5 = {0, 1, 2, 3, 4}
Modulo 5 gerechnet gilt beispielsweise
3 + 4 = 2 und
3 · 3 = 4
Die Menge ℤn bildet mit den Verknüpfungen +n und ·n sowie 0 und 1 als neutralen Elementen einen Ring mit Eins und, wenn n eine Primzahl ist, sogar einen Körper.
Berechnungen modulo n
Da die Addition und die Multiplikation verknüpfungstreu bezüglich der Relation ≡ (mod n) sind, können bei Additionen und Multiplikationen modulo n beliebige Zwischenergebnisse modulo n reduziert werden, ohne dass sich am Ergebnis etwas ändert.
Beispiel: Welcher Wochentag ist heute in drei Jahren und 40 Tagen? Wenn keine Schaltjahre zu berücksichtigen sind, müssen wir ausgehend vom heutigen Wochentag um
(3·365 + 40) mod 7
Tage weiterzählen. Statt aber 3·365 + 40 zu berechnen, reduzieren wir bereits die Zwischenergebnisse modulo 7:
(3·365 + 40) mod 7 = (3·(365 mod 7) + (40 mod 7)) mod 7
= (3·1 + 5) mod 7) = 8 mod 7 = 1
Wenn also heute Mittwoch ist, so ist in drei Jahren und 40 Tagen Donnerstag.
Auch für Berechnungen modulo n gelten die Potenzgesetze, d.h. für beliebige Zahlen a, x, y ∈ ℤ gilt:
ax+y ≡ ax · ay (mod n) sowie
ax·y ≡ (ax)y (mod n)
Aber Achtung: Die Verknüpfungstreue von ≡ (mod n) erstreckt sich nicht auf den Exponenten. Der Exponent darf nicht modulo n reduziert werden. Addition, Subtraktion und Multiplikation von Exponenten müssen in ℤ durchgeführt werden.
Beispiel: Sei n = 5. Dann gilt beispielsweise
3 ≡ 128 ≡ 27 ≢ 27 mod 5 ≡ 22 ≡ 4 (mod 5)
Ebenso gilt für das multiplikativ inverse Element 2-1 der Zahl 2:
3 ≡ 2-1 ≢ 2-1 mod 5 ≡ 24 ≡ 1 (mod 5)
Bei Berechnungen modulo n bedeutet die Schreibweise a-x also nicht, dass -x das modulo n additiv inverse Element von x ist, also n-x, sondern -x ist das additiv inverse Element von x in ℤ.
Später werden wir sehen, dass es dennoch möglich ist, den Exponenten zu reduzieren, aber nicht modulo n, sondern modulo φ(n). Hierbei ist φ die eulersche Phi-Funktion. Für alle n ∈ ℕ gibt φ(n) die Anzahl der Zahlen aus {0, ..., n-1} an, die teilerfremd zu n sind.
Beispielsweise sind die Zahlen 1, 2, 3, 4 teilerfremd zu n = 5. Daher beträgt φ(5) = 4. Die obigen Gleichungen gehen auf, wenn die Exponenten modulo 4 reduziert werden.
Literatur
Die Mathematik, die Sie in der Informatik brauchen, finden Sie beispielsweise in folgenden Büchern. Wenn Sie noch am Anfang stehen, ist empfehlenswert:
[Lan 21] H.W. Lang: Vorkurs Informatik für Dummies. Wiley (2021)
Lesen Sie zum Thema Teilbarkeit und Modulo-Rechnung auch Kapitel 17 in meinem Buch Vorkurs Informatik für Dummies.
1) Diese Definition verwendet nicht die Relation > ("größer"); sie gilt daher auch in anderen mathematischen Strukturen als ℤ, z.B. in Polynomringen. Außerdem gilt nach dieser Definition in natürlicher Weise ggt(0, 0) = 0.
Weiter mit: [Wort, Sprache, Grammatik] [Literatur] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 12.06.1999 Updated: 10.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden