Mathematische Grundlagen

Teilbarkeit, Kongruenz modulo n

 aufwärts

Teilbarkeit

Definition:  Seien a, d Element  ganze Zahlen 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. Gleicher­maß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  ganze Zahlen gilt

a | b   und   b | c    folgt    a | c.

Definition:  Die Teiler 1, -1, a und -a sind die trivialen Teiler von a. Die nicht­trivialen 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 zusammen­gesetzt.

Die 1 spielt eine Sonderrolle und ist weder Primzahl noch zusammen­gesetzt. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

 

Größter gemeinsamer Teiler

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

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. Eindeutig­keit wird erreicht, indem der nicht­negative größte gemeinsame Teiler als der größte gemeinsame Teiler angesehen wird.

Definition:  Die Funktion ggt :  ganze Zahlen ×  ganze Zahlen Pfeil nach rechts natürliche Zahlen0 ist definiert durch

ggt(a, b) = g,

wobei g größter nicht­negativer 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.

Der größte gemeinsame Teiler von zwei nicht­negativen ganzen Zahlen lässt sich effizient mit dem euklidischen Algorithmus berechnen.

Kongruenz modulo n

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 beispiels­weise:

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

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

Satz:  Die Relation  kongruent  (mod n) ist eine Kongruenz­relation, d.h. eine verknüpfungs­treue Äquivalenz­relation, denn es gilt für alle a, a', b, b' Element  ganze Zahlen

a kongruent a' (mod n)   und   b kongruent b' (mod n)    folgt    a + b  kongruent  a' + b'   (mod n)   sowie

a kongruent a' (mod n)   und   b kongruent b' (mod n)    folgt    a · b  kongruent  a' · b'   (mod n)

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

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

Es ist zu unter­scheiden zwischen der Operation mod n und der Relation  kongruent  (mod n). Wenn a mod n = b ist, so ist zwar stets a kongruent b (mod n), umgekehrt jedoch nicht, denn z.B. ist 8 kongruent 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  kongruent  b  (mod n)   genau dann wenn   a mod n  =  b mod n

Bemerkung:  Die Relation  kongruent  (mod n) ist eine Äquivalenz­relation. Eine Äquivalenz­relation bewirkt stets eine Klassen­einteilung der Grundmenge in Klassen äquivalenter Elemente. Die Äquivalenz­klassen der Relation  kongruent (mod n) enthalten jeweils diejenigen Zahlen, die bei Division durch n denselben Rest ergeben, sie heißen deshalb Restklassen. Die kleinste nicht­negative Zahl in jeder Restklasse ist 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.

Beispiel:  Es sei n = 2. Die Relation  kongruent  (mod 2) teilt  ganze Zahlen 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 ganze Zahlenn

Die Menge {0, 1, 2, ..., n-1} der Repräsentanten der Restklassen modulo n bildet die Menge  ganze Zahlenn.

Definition:  Sei n Element natürliche Zahlen. Die Menge  ganze Zahlenn ist definiert als

 ganze Zahlenn  =  {0, 1, 2, ..., n-1}

Definition:  Sei n Element natürliche Zahlen. Auf der Menge  ganze Zahlenn werden Ver­knüpfungen +n (Addition modulo n) und ·n (Multi­plikation 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

 ganze Zahlen5  =  {0, 1, 2, 3, 4}

Modulo 5 gerechnet gilt beispiels­weise

3 + 4  =  2   und

3 · 3  =  4

Die Menge  ganze Zahlenn bildet mit den Ver­knü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 Multi­plikation verknüpfungs­treu bezüglich der Relation  kongruent  (mod n) sind, können bei Additionen und Multi­plikationen modulo n beliebige Zwischen­ergebnisse 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ück­sichtigen 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 Zwischen­ergebnisse 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 Potenz­gesetze, d.h. für beliebige Zahlen a, x, y Element  ganze Zahlen gilt:

ax+y   kongruent   ax · ay   (mod n)    sowie

ax·y   kongruent   (ax)y   (mod n)

 

Aber Achtung: Die Verknüpfungs­treue von  kongruent  (mod n) erstreckt sich nicht auf den Exponenten. Der Exponent darf nicht modulo n reduziert werden. Addition, Subtraktion und Multi­plikation von Exponenten müssen in  ganze Zahlen durchgeführt werden.

Beispiel:  Sei n = 5. Dann gilt beispiels­weise

3  kongruent  128  kongruent  27 nicht kongruent 27 mod 5  kongruent  22  kongruent  4   (mod 5)

Ebenso gilt für das multi­plikativ inverse Element 2-1 der Zahl 2:

3  kongruent  2-1 nicht kongruent 2-1 mod 5  kongruent  24  kongruent  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.

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 Element natürliche Zahlen gibt φ(n) die Anzahl der Zahlen aus {0, ..., n-1} an, die teilerfremd zu n sind.

Beispiels­weise 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 beispiels­weise in folgenden Büchern. Wenn Sie noch am Anfang stehen, ist empfehlens­wert:

[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.

[Weitere Informationen]

Buch  

1)  Diese Definition verwendet nicht die Relation > ("größer"); sie gilt daher auch in anderen mathe­matischen Strukturen als  ganze Zahlen, z.B. in Polynom­ringen. Außerdem gilt nach dieser Definition in natürlicher Weise ggt(0, 0) = 0.

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 12.06.1999   Updated: 25.08.2021
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

 

 

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik