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 a 2 mod b

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

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

Rechnen mit Zahlenkongruenzen

Wenn a 1 r 1 mod b und a 2 r 2 mod b ist, so gilt:

  1. a 1 + a 2 r 1 + r 2 mod b
  2. a 1 - a 2 r 1 - r 2 mod b
  3. a 1 a 2 r 1 r 2 mod b

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

  • 93 3 mod 5 und 17 2 mod 5, also
    93 + 17 3 + 2 0 mod 5 (110 0 mod 5)
    93 - 17 3 - 2 1 mod 5 (76 1 mod 5)
    93 17 3 2 1 mod 5 (1581 1 mod 5).
  • 12 3 und 21 3 mod 9, also
    12 21 252 3 3 9 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 + ... + a 2 10 2 + a 1 10 + a 0
nun gilt: 10 1 mod 9 und damit 10 10 10 n 1   mod 9 ;
daraus folgt: z a n + a n 1 + ... + a 2 + a 1 + a 0   0 mod  9
und 9 | z genau dann, wenn a n + a n 1 + ... + a 2 + a 1 + a 0 0  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:
10 0 1 mod 13 10 1 10 mod 13 10 2 9 mod 13 10 3 12 1 mod 13 10 4 3 10 mod 13 10 5 4 9 mod 13 10 6 1 mod 13 10 7 10 mod 13 10 8 9 mod 13 10 9 12 1 mod 13 10 10 3 10 mod 13 10 11 4 9 mod 13 u s w .
Für eine Zahl z = a n 10 n + a n 1 10 n 1 + ... + a 2 10 2 + a 1 10 + a 0 ist danach genau z 0 mod 13, wenn für die Zahl x, die wie nachfolgend angegeben zu ermitteln ist, x 0 mod 13 gilt.
x = ( a 0 + 10 a 1 + 9 a 2 ) ( a 3 + 10 a 4 + 9 a 5 ) + ( a 6 + 10 a 7 + 9 a 8 ) ( a 9 + 10 a 10 + 9 a 11 ) + ....

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

Man rechnet x = ( 9 + 10 0 + 9 6 ) ( 3 + 7 10 + 9 9 )
und erhält x = ( 9 + 54 ) ( 3 + 70 + 81 ) = 63 154 = 91 = 7 13
Es gilt also x 0 mod 13, d. h., z ist durch 13 teilbar.
( 973 609 = 74 893 13 )

Stand: 2010
Dieser Text befindet sich in redaktioneller Bearbeitung.

Lexikon Share
Mathe Note verbessern?
 

Kostenlos bei Duden Learnattack registrieren und ALLES 48 Stunden testen.

Kein Vertrag. Keine Kosten.

  • 40.000 Lern-Inhalte in Mathe, Deutsch und 7 weiteren Fächern
  • Hausaufgabenhilfe per WhatsApp
  • Original Klassenarbeiten mit Lösungen
  • Deine eigene Lern-Statistik
  • Kostenfreie Basismitgliedschaft

Einloggen