Zahlenkongruenzen

Kongruenz von Zahlen

Zwei Zahlen $a_1$ und $a_2$ heißen kongruent nach dem Modul b
(modulo b), wenn sie bei Division durch b den gleichen Rest lassen (gleichrestig sind), also zur gleichen Restklasse modulo b gehören.
Man schreibt: $a_1$ $\equiv$ $a_2$ mod b

Beispiele:
7 $\equiv$92 mod 5; 13 $\equiv$45 mod 8; 21 $\equiv$77 mod 7

Zahlenkongruenzen lassen sich gut zum Lösen diophantischer Gleichungen nutzen.

Rechnen mit Zahlenkongruenzen

Wenn $a_1$ $\equiv$ $r_1$ mod b und $a_2$ $\equiv$ $r_2$ mod b ist, so gilt:

1. $a_1$+ $a_2$ $\equiv$ $r_1$+ $r_2$ mod b
2. $a_1$- $a_2$ $\equiv$ $r_1$- $r_2$ mod b
3. $a_1\cdot a_2\equiv r_1\cdot r_2$ mod b

Die Sätze 1 und 3 lassen sich auch auf mehrere Kongruenzen ausdehnen.

• 93 $\equiv$3 mod 5 und 17 $\equiv$2 mod 5, also
  93 + 17 $\equiv$ 3 + 2 $\equiv$ 0 mod 5 (110 $\equiv$0 mod 5)
  93 - 17 $\equiv$ 3 - 2 $\equiv$1 mod 5 (76 $\equiv$1 mod 5)
  $93\cdot 17\equiv 3\cdot 2\equiv 1$ mod 5 (1581 $\equiv$1 mod 5).
• 12 $\equiv$3 und 21 $\equiv$3 mod 9, also
  $12\cdot 21\equiv 252\equiv 3\cdot 3\equiv 9\equiv 0$ mod 9

Das zweite Beispiel zeigt, dass beim Rechnen mit Kongruenzen mod 9 ein Produkt null sein kann, obwohl keiner der Faktoren null ist. Die vom Rechnen in den „normalen“ Zahlenbereichen bekannte Nullteilerfreiheit ist also nicht mehr vorhanden. Sie existiert nur, wenn der Modul eine Primzahl ist.

Mithilfe von Zahlenkongruenzen lassen sich Teilbarkeitsregeln beweisen bzw. herleiten.

Bekanntlich ist eine Zahl genau dann durch 9 teilbar, wenn ihre Quersumme durch 9 teilbar ist (Darstellung im dekadischen Positionssystem).

Beweis:
$z=a_n{10}^n+a_{n-1}{10}^{-1}+\mathrm{...}+a_2{10}^2+a_{1}10+a_0$
nun gilt: 10 $\equiv$1 mod 9 und damit $10\cdot 10\equiv {10}^n\equiv 1\mathrm{mod}9$;
daraus folgt: $z\equiv a_n+a_{n-1}+\mathrm{...}+a_2+a_1+a_0\equiv 0\text{mod }9$
und $9|z$ genau dann, wenn $a_n+a_{n-1}+\mathrm{...}+a_2+a_1+a_0\equiv 0\text{ mod 9}$, d. h., wenn die Summe $a_i$ (die Quersumme) ein Vielfaches von 9, also durch 9 teilbar ist.

Es soll eine Teilbarkeitsregel für die Zahl 13 hergeleitet werden.

Es gilt:
$\begin{array}{l}{10}^0\equiv 1\mathrm{mod}13{10}^1\equiv 10\mathrm{mod}13{10}^2\equiv 9\mathrm{mod}13{10}^3\equiv 12\equiv -1\mathrm{mod}13\\ {10}^4\equiv 3\equiv -10\mathrm{mod}13{10}^5\equiv 4\equiv -9\mathrm{mod}13\\ {10}^6\equiv 1\mathrm{mod}13{10}^7\equiv 10\mathrm{mod}13{10}^8\equiv 9\mathrm{mod}13{10}^9\equiv 12\equiv -1\mathrm{mod}13\\ -{10}^{10}\equiv 3\equiv -10\mathrm{mod}13{10}^{11}\equiv 4\equiv -9\mathrm{mod}13\\ usw.\end{array}$
Für eine Zahl $z=a_n\cdot {10}^n+a_{n-1}\cdot {10}^{n-1}+\mathrm{...}+a_2\cdot {10}^2+a_1\cdot 10+a_0$ ist danach genau z $\equiv$0 mod 13, wenn für die Zahl x, die wie nachfolgend angegeben zu ermitteln ist, x $\equiv$0 mod 13 gilt.
$\begin{array}{l}x=\left(a_0+10a_1+9a_2\right)-\left(a_3+10a_4+9a_5\right)\\ +\left(a_6+10a_7+9a_8\right)-\left(a_9+10a_{10}+9a_{11}\right)+\mathrm{....}\end{array}$

Es soll untersucht werden, ob die Zahl z = 973609 durch 13 teilbar ist.

Man rechnet $x=\left(9+10\cdot 0+9\cdot 6\right)-\left(3+7\cdot 10+9\cdot 9\right)$
und erhält $x=\left(9+54\right)-\left(3+70+81\right)=63-154=-91=-7\cdot 13$
Es gilt also x $\equiv$0 mod 13, d. h., z ist durch 13 teilbar.
$\left(973609=74893\cdot 13\right)$