Grundlagen

Mathematik Didaktik Seminar

Motivation: Die Uhr zeigt 3 Uhr. Wieviel Uhr ist es 106 Stunden später?

Einige Probleme der Zahlentheorie erscheinen im Prinzip einfach, bereiten bei der Lösung aber leichte Schwierigkeiten. Soll man z.B. berechnen,

• ob 222⁵⁵⁵ + 555²²² durch 7 teilbar ist und
• auf welche Ziffer 333²²² endet

benötigt man weiteres mathematisches Rüstzeug, denn es leuchtet ein, dass man mit solch großen Zahlen in der Praxis nicht rechnen kann.
Der "Trick" liegt darin, nicht alle ganzen Zahlen zu betrachten, sondern sie nach dem Rest einzuteilen, den sie bei der Division durch eine bestimmte Zahl haben.
Für diese Einteilung lässt sich jede natürliche Zahl m benutzen. Alle ganzen Zahlen die beim Teilen durch m denselben Rest lassen werden in einer Gruppe, der sogenannten Restklasse von m, zusammengefasst. Zwei Zahlen aus derselben Restklasse werden als kongruent (lat.:übereinstimmend) bezüglich eines Moduls m bezeichnet.
Wählt man m=8, so lassen die Zahlen 5, 13, 21, 29, aber auch -3, -11, -19 bei der Division durch m denselben Rest 5 (beachte: -3 = -1·8 + 5).
Ebenso gehören die Zahlen 3, 11, 19, -5, -13, -21 in eine Restklasse, sie haben den Rest 3.
Bezeichnet man die Restklassen von m nach dem kleinsten positiven Rest, findet man genau m Restklassen 0*, 1*, ..., (m-1)* und es gilt:

0*=	{..., -5·m, -4·m, -3·m, -2·m, -m, 0, m, 2·m, 3·m, 4·m, 5·m, ...}
	={ x | x=k·m+0 und kZ}
1*=	{..., -5·m+1, -4·m+1, -3·m+1, -2·m+1, -m+1, 1, m+1, 2·m+1, 3·m+1, 4·m+1, 5·m+1, ...}
	={ x | x=k·m+1 und kZ}
....	......................................
(m-1)*=	{..., -5·m+(m-1), -4·m+(m-1), -3·m+(m-1), -2·m+(m-1), -m+(m-1), (m-1), m+(m-1), 2·m+(m-1), 3·m+(m-1), 4·m+(m-1), 5·m+(m-1), ...}
	={ x | x=k·m+(m-1) und kZ}

Man schreibt formal:

Für diese a,b gilt

Umgeformt erhält man

D.h. (a-b) ist ein Vielfaches von m, was gleichbedeutend ist mit

Somit ist folgende Aussage äquivalent :

Beispiele:

Wir können jetzt auch die Eingangs gestellte Frage beantworten:
(3+106) mod 12 = 109 mod 12 = 1 mod 12
Damit steht der Zeiger auf der 1.

Übungen:

Bestimme alle nN mit 345·n º 7 mod 133!

Bestimme alle nN mit 22·n º 1 mod 21!