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.

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.

Die Relation  kongruent  (mod n) ist eine Äquivalenz­relation. Eine Äquivalenz­relation bewirkt 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 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 ganze Zahlenn 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 ganze Zahlen2 = {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   0kleiner gleichb < n,

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

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:  Die Relation  kongruent  (mod n) ist eine Kongruenz­relation, d.h. eine verknüpfungs­treue Äquivalenz­relation, denn es gilt für alle a, b, c, d Element ganze Zahlen

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

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

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.

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 Ver­knüpfungstreue 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.


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   ©   Created: 12.06.1999   Updated: 21.05.2016
Valid HTML 4.01 Transitional


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

 

Ebenfalls ganz neu:

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