Mathematische Grundlagen

Teilbarkeit, Kongruenz modulo n

Definition: Seien a, d Element 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 genau dann wenn es existiert k Element ganze Zahlen : 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 ganze Zahlen ist transitiv, d.h. für alle a, b, c Element gilt

a | b und b | c folgt 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 Element natürliche Zahlen , 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, ...

Größter gemeinsamer Teiler

Definition: Seien a, b Element ganze Zahlen . Eine Zahl d Element 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 Element ganze Zahlen . Eine Zahl g Element heißt größter gemeinsamer Teiler von a und b, wenn für alle d Element gilt

d | a und d | b genau dann wenn d | g,

d.h. alle gemeinsamen Teiler von a und b sind auch Teiler von g, und alle Teiler von g, also insbesondere g selbst, sind auch gemeinsame Teiler von a und b.¹)

In ganze Zahlen 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 : ganze Zahlen kreuz natürliche Zahlen ₀ 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 Element ganze Zahlen :

ggt(0, a) = |a|

Insbesondere gilt

ggt(0, 0) = 0

Definition: Zwei Zahlen a, b Element ganze Zahlen werden als teilerfremd bezeichnet, wenn ggt(a, b) = 1 ist.

Definition: Sei n Element natürliche Zahlen . Die Relation kongruent modulo n auf der Menge der ganzen Zahlen ganze Zahlen ist wie folgt definiert:

a kongruent b (mod n) genau dann wenn n | a – b

für alle a, b Element ganze Zahlen .

Zwei Zahlen sind also kongruent (modulo n), wenn ihre Differenz durch n teilbar ist.

Beispiel: Es gilt beispielsweise:

17 kongruent 2 (mod 5), 2 17 (mod 5), 6 0 (mod 2), -6 8 (mod 2)

Dagegen gilt nicht: 17 kongruent -17 (mod 5), denn 17 – (-17) = 34, und 34 ist nicht durch 5 teilbar.

Die Relation kongruent (mod n) ist eine Äquivalenzrelation. Eine Äquivalenzrelation bewirkt 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 heißt Repräsentant der Restklasse.

Die Relation kongruent (mod n) teilt ganze Zahlen in n Restklassen mit den Repräsentanten 0, 1, 2, ..., n-1 ein. Die Menge der Repräsentanten {0, 1, 2, ..., n-1} wird mit _n bezeichnet.

Beispiel: Es sei n = 2. Die Relation kongruent (mod 2) teilt ganze Zahlen in zwei Restklassen ein: die geraden und die ungeraden Zahlen. Der Repräsentant der geraden Zahlen ist die 0, der Repräsentant der ungeraden Zahlen die 1. Somit ist also ₂ = {0, 1}.

Definition: Sei a Element ganze Zahlen , n Element natürliche Zahlen . Die Operation mod ist wie folgt definiert:

a mod n = b genau dann wenn a kongruent b (mod n) und 0 kleiner gleich b < n,

d.h. a mod n liefert den Repräsentanten der Klasse, in der a liegt.

Es ist zu unterscheiden zwischen der Operation mod n und der Relation kongruent (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 ungleich 6.

Satz: Die Relation kongruent (mod n) ist eine Kongruenzrelation, d.h. eine verknüpfungstreue Äquivalenzrelation, denn es gilt für alle a, b, c, d Element ganze Zahlen

a kongruent b (mod n) und c d (mod n) folgt a + c b + d (mod n) sowie

a kongruent b (mod n) und c d (mod n) folgt a · c b · d (mod n).

Definition: Sei n Element natürliche Zahlen . Auf der Menge ganze Zahlen _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.

Die Menge ganze Zahlen _n bildet mit der Verknüpfung +_n und 0 als neutralem Element eine abelsche Gruppe.

Da die Addition und die Multiplikation verknüpfungstreu bezüglich der Relation kongruent (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 Element ganze Zahlen gilt:

a^x+y kongruent a^x · a^y (mod n) sowie

a^x·y kongruent (a^x)^y (mod n)

Aber Achtung: Die Verknüpfungstreue von kongruent (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 ganze Zahlen durchgeführt werden.

Beispiel: Sei n = 5. Dann gilt beispielsweise

3 kongruent 128 2⁷ nicht kongruent 2^{7 mod 5} 2² 4 (mod 5)

Ebenso gilt für das multiplikativ inverse Element 2^-1 der Zahl 2:

3 kongruent 2^-1 nicht kongruent 2^{-1 mod 5} 2⁴ 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 ganze Zahlen .

¹) Diese Definition verwendet nicht die Relation > ("größer"); sie gilt daher auch in anderen mathematischen Strukturen als ganze Zahlen , z.B. in Polynomringen.

Weiter mit: [Wort, Sprache, Grammatik] [Literatur] oder