Kongruenzen ganzer Zahlen

In der Zahlentheorie bezeichnet man zwei oder mehr ganze Zahlen genau dann als kongruent (zueinander), wenn sie bei Division durch eine Zahl m den gleichen Rest haben. Ob zwei Zahlen kongruent zueinander sind ist also abhängig von dem Rest den sie bei der Divison durch m haben. Ist dieser gleich sind beide Zahlen kongruent bezüglich m, andernfalls sind sie inkongruent. In diesem Artikel betrachten wird ganze Zahlen und ihre Beziehung zueinander.

Allgemeine Schreibweise:

$$a\equiv b\;mod\;m\;$$

wobei mod für die mathematische Modulo-Funtion steht.

Beispiel:

$$9\;\equiv\;23\;mod\;\mathbf7$$

Erklärung

…weil beide den gleichen Rest 2 haben: $$\begin{array}{l}9\;:\;7\;=\;1\;R\;\mathbf2\;\\23\;:\;7\;=\;3\;R\;\mathbf2\;\end{array}$$

Ausschlaggebend ist nicht der Faktor wie oft die 7 in die 9 geht. Lediglich der Rest (hier 2) ist von Bedeutung.

Gegenbeispiel:

$$9\;\not\equiv\;24\;mod\;7\;$$

Erklärung

$$\begin{array}{l}9\;:\;7\;=\;1\;R\;\mathbf2\;\\24\;:\;7\;=\;3\;R\;\mathbf3\;\end{array}$$

Da beide Divisonen einen unterschiedlichen Rest liefern (2 ungleich 3) ist 9 inkongruent zu 24.

Die Modulo-Funktion

Unter der mathematischen Modulo-Funktion versteht man eine Funktion, die den Rest aus der Division ganzer Zahlen zurück gibt.

Es gibt immer m "Reste". Diese bezeichnet man als Restklassen: $$\overline x\;=\;\left\{\overline0,\overline1,\overline2, … ,\overline {m-1}\right\}$$

Wir schauen uns nun die Restklassen bei der Division durch m = 3 und m = 7 an. Die Liste kann beliebig vorgesetzt werden. Die Restklassen wiedeholen sich kontinuierlich.

Beispiel 1: Wir dividieren durch m = 3

$$\begin{array}{l}0\;:\;3\;=\;0\;R0\\1\;:\;3\;=\;0\;R\;1\\2\;:\;3\;=\;0\;R\;2\\3\;:\;3\;=\;1\;R\;0\;\\4\;:\;3\;=\;1\;R\;1\;\\…\\\end{array}$$

Die Restklassen bei m = 3 sind also $$\overline x\;=\;\left\{\overline0,\overline 1,\overline 2\right\}$$

Beispiel 2: m = 7

$$\begin{array}{l}0\;:\;7=\;0\;R\;0\\1\;:\;7=\;0\;R\;1\\2\;:\;7=\;0\;R\;2\\3\;:\;7=\;0\;R\;3\\4\;:\;7=\;0\;R\;4\\5\;:\;7=\;0\;R\;5\\6\;:\;7=\;0\;R\;6\\7\;:\;7=\;0\;R\;0\\8\;:\;7=\;0\;R\;1\\9\;:\;7=\;0\;R\;2\\…\\\\\end{array}$$ Hier gibt es 7 Restklassen. $$\overline x\;=\;\left\{\overline0,\overline1,\overline2,\overline3,\overline4,\overline5,\overline6,\right\}$$

Es werden also alle Zahlen mit dem gleichen Rest als kongruent bezeichnet. So sind im Beispiel 2 die Zahlen 2 und 9 kongruent modulo 7, da bei bei der Division durch 7 den Rest 2 aufweisen.

Differenz kongruenter Zahlen

Sind zwei Zahlen zueinander kongruent bedeutet das außerdem, dass die Differenz von a und b ein ganzahliges Vielfaches von m ist.

Beispiel:$$9\;\equiv\;23\;mod\;\mathbf7$$

$$23\;-\;9\;=\:14\;=\:(2\;\cdot\;7)$$

hier das 2fache von 7.

Da a und b aus der Menge der ganzen Zahlen sind, kann es auch vorkommen, dass a und/oder b negativ sind. Auch hier kann die Beziehung auf kongruenz geprüft werden:

Beispiel 1 :

$$-15\;\equiv-9\;mod\;6$$

Erklärung

Beide haben den gleichen Rest 3:

$$-15\;:\;6\;\;=\;(-2)\;R\;3$$ $$-9\;\;:\;\;6\;\;=\;(-1)\;R\;3$$

Beispiel 2:

$$-15\;\equiv\;21\;mod\;6$$

Erklärung

Beide haben den gleichen Rest 3:

$$-15\;:\;6\;\;=\;(-2)\;R\;3$$ $$21\;\;:\;\;6\;\;=\;3\;R\;3$$

Der Grund dafür liegt in der Art wie die Ganzzahldivision definiert ist. Dabei muss der Rest immer das gleiche Vorzeichen wie der Divisor haben. Hier + 6, welcher positiv ist.

Mit Restklassen kann man rechnen:

Beispiel m = 7

Bei m = 7 haben wir $$\overline x\;=\;\left\{0,1,2,3,4,5,6\right\}$$ Restklassen.

%%\circ%%

%%\overline0%%

%%\overline 1%%

%%\overline 2%%

%%\overline 3%%

%%\overline 4%%

%%\overline 5%%

%%\overline 6%%

$$\overline 0$$

$$\overline 0$$

$$\overline 0$$

$$\overline 0$$

$$\overline 0$$

$$\overline 0$$

$$\overline 0$$

$$\overline 0$$

$$\overline 1$$

$$\cdot$$

$$\overline 1$$

$$\overline 2$$

$$\overline 3$$

$$\overline 4$$

$$\overline 5$$

$$\overline 6$$

$$\overline 2$$

$$\cdot$$

$$\cdot$$

$$\overline 4$$

$$\overline 6$$

$$\overline 1$$

$$\overline 3$$

$$\overline 5$$

$$\overline 3$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\overline 2$$

$$\overline 5$$

$$\overline 1$$

$$\overline 4$$

$$\overline 4$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\overline 2$$

$$\overline 6$$

$$\overline 3$$

$$\overline 5$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\overline 3$$

$$\overline 2$$

$$\overline 6$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\cdot$$

$$\overline 1$$

Erklärung

Am Beispiel des letzten Eintrags: $$\;\overline6\cdot\overline6=\overline{36}\;=\overline1$$ Denn $$\;36\div7\;=\;5\;R\;1\;\Rightarrow\;\overline x\;=\overline1$$

Die Einträge in der Multiplikationstafel der Restklassen zu m = 7 ist an der Diagonale gespiegelt, weshalb die Einträger des oberen Dreiecks ausreichen.

Nullteiler und Inverse Elemente

Aus der obigen Multiplikationstafel kann man die Nullteiler und die inverse Elemente entnehmen.

Nullteiler

Als Nullteiler werden alle Elemente bezeichnet, die bei der Multiplikation die Restklasse 0 haben. $$\;\overline0\cdot\overline 0 =\overline{0}$$ Da in diesem Beispiel m = 7 eine Primzahl ist, gibt es keine Teiler aus 1 und 7 selbst, weshalb es nur den triviale Nullteiler gibt.

Inverses Element

Als inverses Element wird eine Zahl x bezeichnet, die bei der Multiplikations das neutrale Elemente bezüglich der Multiplikation (hier 1) ergibt.

$$\;a\cdot x=\;1$$ für ein beliebies a.

Aus der obigen Multiplikationstafel sind also folgende Zahlen die inverses Elemente: $$\;x=\;\left\{1,2,3,4,5,6\right\}$$ $$\;\overline1\cdot\overline1=\overline1$$ $$\;\overline2\cdot\overline4=\overline1$$ $$\;\overline3\cdot\overline5=\overline1$$ $$\;\overline6\cdot\overline6=\overline1$$

Falls m eine Primzahl ist ( wie in diesem Beispiel) dann gibt es 1,…,(m-1) invertierbare Elemente. Das liegt daran, dass die invertierbaren Elemente alle zu 7 teilerfremde Zahlen sind. Ist m keine Primzahlen, so fallen alles Teiler und deren Vielfachen heraus.

Kommentieren Kommentare