Kap 3.3
Der Chinesische Restsatz (2)

Wir wenden uns nochmals den sogenannten "simultanen Kongruenzen" zu, die wir unter der Überschrift "Chinesischer Restsatz" schon in 2.4 behandelt haben. Wir werden jetzt zwei Verfahren kennenlernen, welche intensiv vom Rechnen mit Kongruenzen Gebrauch machen.

1.Verfahren: Das 1. Verfahren wird am einfachsten an einem Beispiel demonstriert:
(1) xº5 mod 7 und (2) xº 3 mod 9: (2) Þ x=9k+3º5 mod 7 (nach(1))
Þ9kº2 mod 7 (wird gelöst wie in 3.1)
Þkº1 mod 7
in die erste Gleichung: x=12 mod 7·9, also x_k=12+63k

AUFGABE 3.25 Löse mit dem 1.Verfahren:
a) xº9 mod 11 Ù xº7 mod 13
b) xº17 mod 19 Ù xº 25 mod 29
c) xº6 mod 53 Ù xº 22 mod 71

Für das nächste Verfahren brauchen wir neben der Kürzungsregel (Satz 3.2, K10) und K6 eine weitere Rechenregeln:

(R) Für ggT(p,q)=1 gilt: xºc mod p Ûqxºqc mod pq

AUFGABE 3.26
Konstruiere 3 Beispiele für (R) und beweise die Regel dann.

Nun können wir das 2.Verfahren demonstrieren:

Gesucht: xº17 mod 19 Ù xº25 mod 29
Wir benutzen (R) und erhalten: 29xº 17·29 Ù19xº 19·25 mod 19·29
Mit (K6) folgt: 10xº18 mod 551
Mit (K10) folgt: 5xº 9º560 mod 551
Wieder mit (K10): xº112 mod 551
Ergebnis: x_k=112+k×551

Das hier benutzte "Kürzungsverfahren" erfordert eine Menge Geschick und führt nicht immer zum Erfolg. Im Zweifelsfall hilft der Berlekamp-Algorithmus weiter. Das Verfahren läßt sich auch mit Erfolg auf mehr als zwei Kongruenzen anwenden.

AUFGABE 3.27
Löse mit dem 2.Verfahren:
a) xº10 mod 31 Ù xº20 mod 39 b) xº50 mod 51 Ù xº55 mod 61
c) xº17 mod 48 Ù xº20 mod 77 d) xº12 mod 27 Ù xº31 mod 55
e) xº10 mod 11 Ù xº11 mod 13 Ù xº12 mod 17

AUFGABE 3.28
Löse die Aufgaben 2.15 und 2.16 mit einem der neuen Verfahren.

Download Kap3_3 (34 KB)

Copyright © Michael Dorner, Januar 2001.