Kap 2.4
DER CHINESISCHE RESTSATZ (1)

In vielen Mathematikbüchern aus alten Zeiten, angefangen bei über 2000 Jahre alten chinesischen Mathematikbüchern (Handbuch der Arithmetik von Sun-Tzun Suan-Ching), aber auch in berühmten "Liber abaci" der Leonardo von Pisa (Fibonacci), finden sich Aufgaben, in denen Zahlen gesucht werden, die bei Division durch verschiedenen andere Zahlen vorgegebene Reste lassen. Fangen wir zur Demonstration mit einem Beispiel an:

"Wie alt bist Du?" wird Daisy von Donald gefragt. "So was fragt man eine Dame doch nicht" antwortet diese. "Aber wenn Du mein Alter durch drei teilst, bleibt der Rest zwei." "Und wenn man es durch fünf teilt?" "Dann bleibt wieder der Rest zwei. Und jetzt sage ich Dir auch noch, daß bei Division durch sieben der Rest fünf bleibt. Nun müßtest Du aber wissen, wie alt ich bin." Weißt der Leser es auch?

Wir wollen hier zwei Verfahren kennenlernen, mit denen man solche Probleme lösen kann.

1. Verfahren: Bei kleinen Zahlen wie im obigen Beispiel kann man vorteilhaft alle Zahlen durchprobieren, die der Bedingung mit dem größten Teiler gehorchen und diese dann auf ihre Eignung bezüglich der anderen Teiler überprüfen. Für die obige Aufgabe ergeben sich der Reihe nach die Zahlen: 5, 12, 19, 26, 33, 40, 47 - und da hat man bereits die gesuchte Zahl. Natürlich kommen nun auch alle Zahlen x_k=47+k·3·5·7 in Frage (allerdings nicht bei der obigen Situation), denn diese hinterlassen ja bei Division durch 3, 5 und 7 denselben Rest.

AUFGABE 2.14
a) Löse: x läßt bei Division durch 7 den Rest 4 und bei Division durch 13 den Rest 10.
b) ebenso: x läßt bei Division durch 11 den Rest 9, bei Division durch 7 den Rest 5 und bei Division durch 3 den Rest 2

Bei großen Divisoren oder mehreren Bedingungen kann das 1. Verfahren schon recht mühsehlig werden. Wir demonstrieren deshalb ein 2.Verfahren an einigen Beispielen. Zuerst werden wir allerdings im Vorgriff auf das nächste Kapitel eine Schreibweise einführen, mit der man Aufgaben dieser Art angenehmer und übersichtlicher formulieren kann. Nehmen wir an, wir suchen die Zahlen x, die bei Division durch 13 den Rest 5 und bei Division durch 11 den Rest 6 lassen. Vom Programmieren kennen wir die Schreibweise x MOD 13 = 5. Wir wandeln in Anlehnung an Gauß die Schreibweise etwas ab (näheres im nächsten Kapitel) und schreiben: xº 5 mod 13 (gelesen "x kongruent 5 modulo 13").

Die obige Aufgabe lautet in dieser Schreibweise: Bestimme alle xÎ Z mit
xº5 mod 13 Ù xº 6 mod 11.
Es ist also x ein Vielfaches von 13 plus 5 und x ein Vielfaches von 11 plus 6. Anders ausgedrückt: Wir suchen a,bÎ Z mit: x=a·13+5=b·11+6 (*). Durch Umformen erhalten wir: 13a-11b=1. Das ist aber ein bekanntes Problem - mit dem BA erhalten wir a=-5 und b=6. In (*) eingesetzt bringt das x=-60. Nach kurzem Stutzen sieht man ein:
-60=-5·13+5 und -60=-6·11+6 - das Ergebnis ist korrekt. Wir hätten jedoch lieber eine kleine positive Lösung. Kein Problem! Zunächst einmal können wir uns klar machen, daß sich alle Lösungen um Vielfache von 11 ·13=143 unterscheiden. Sind nämlich x und y zwei Lösungen des Problems, so lassen x und y jeweils denselben Rest bei Division durch 13 und 11. Also läßt x-y bei Division durch 11 und 13 den Rest 0, ist also durch 11 teilbar und durch 13 teilbar, d.h. x-y=k·11·13 oder x=y+k·11 ·13. Damit erhalten wir nun alle Lösungen der Aufgabe durch x_k=-60+k·143=83+k·143.

AUFGABE 2.15
Bestimme alle x mit:
a) xº7 mod 13 Ùxº17 mod 23
b) xº2 mod 11 Ù xº1 mod 7
c) xº3 mod 7 Ù xº12 mod 13
d) xº48 mod 95 Ù xº37 mod 81
e) xº100 mod 127 Ù xº102 mod 113

Ist allgemein die Aufgabe xºa mod s Ù xºb mod t gegeben, so führt dies wie im obigen Beispiel auf die Gleichung: x=k·s+a=l·t+b Û k·s-l·t=b-a. Diese ist nach Satz 2.2 dann und nur dann in Z lösbar, wenn b-a durch den ggT(s,t) teilbar ist, insbesondere also immer dann, wenn s und t relativ prim sind. Das halten wir in einem Satz fest:

SATZ 2.3  (Chinesischer Restsatz - Satz über simultane Kongruenzen)
Sind s und t teilerfremd, so existiert eine Lösung z des Systems von Kongruenzen xº a mod s Ù xº b mod t. Man erhält dann alle Lösungen durch x_k=z+k·s·t

Bemerkung: Man kann durch geeignete Wahl von k immer erreichen, daß 0£ z<s·t ist. Darauf wollen wir bei allen Lösungen achten.

AUFGABE 2.16
Suche alle x mit
a) xº217 mod 373 Ù xº25 mod 251
b) xº16 mod 88 Ù xº37 mod 55
c) xº281 mod 389 Ù xº269 mod 457
d) xº15 mod 88 Ù xº37 mod 55

Für Aufgaben mit mehr als drei Bedingungen ändern wir das Verfahren etwas ab.

Gesucht sind alle Zahlen x mit xº 3 mod 5, xº7 mod 11 und xº 1 mod 13. Um nun eine Lösung x zu finden, starten wir mit dem Ansatz:
x=11·13·a+5·13·b +5·11·c  ,a,b,c ÎZ   (**)
Für diese Zahl x gilt dann: xº 143a mod 5. Wir haben nun a so zu bestimmen, daß 143a den Rest 3 bei Division durch 5 läßt, also: 143a=k ·5+3 Û143a-5k=3. Hier können wir nun unser eben erworbenes Wissen über Diophantische Gleichungen ins Spiel bringen:

Wir erhalten a₀=2 (k brauchen wir gar nicht) und damit a=6. Entsprechend bearbeiten wir die Gleichung (**) bez. 11 und 13. Wir erhalten x mod 11=65b. Das soll den Rest 7 bei Division durch 11 lassen, was uns auf 65b-11k=7 führt. Mit dem BA erhalten wir b₀=-1 und damit b=-7. Entsprechend verfahren wir mit 13. Die Gleichung 55c-13k=1 führt auf c =-4.

Eingesetzt in (**) bringt das x=143·6+65·(-7)+55·(-4)=183. Tatsächlich gilt: 183º3 mod 5; 183º 7 mod 11 und 183º 1 mod 13, d.h. 183 ist eine Lösung. Wegen (*) sind damit alle Zahlen x_k=183+715k Lösungen des Problems.

AUFGABE 2.17
Bestimme x mit:
a) xº3 mod 7; xº 12 mod 13; xº1 mod 5
b) xº3 mod 7; xº 5 mod 12; xº10 mod 19
c) xº20 mod 23; xº 20 mod 31; xº20 mod 37
d) xº10 mod 15; xº 12 mod 19; xº20 mod 28
e) xº7 mod 12; xº 12 mod 19; xº19 mod 23

Hat man mehr als drei Reste gegeben, sucht man sinnvollerweise erst mal alle Zahlen, die die ersten zwei oder drei Bedingungen erfüllen und dann diejenigen, die die weiteren Bedingungen erfüllen. Dazu ein Beispiel:

Es sei xº1 mod 3, xº 3 mod 5, xº5 mod 7 und xº7 mod 11
Wir fangen mit der ersten und der letzen Bedingung an und finden mit dem ersten Verfahren sofort 7 als erste Lösung. Also gilt für alle Lösungen bezüglich dieser Bedingungen: xº7 mod 33
Ebenso finden wir für die "mittleren" Bedingungen mit dem 1.Verfahren der Reihe nach:
5,12,19,26,33 - also xº33 mod 35
Nun setzen wir an: x=33a+7=35b+33. Das führt auf die diophantische Gleichung:
35b-33a=-26 mit der Lösung b₀=-16, also b=416 und damit x₀=14593=12·1155+733. Damit sind alle Lösungen des Problems durch x_k=733+k·1155 gegeben.

Man hätte auch direkt nach dem 2.Verfahren vorgehen können. Wir geben deshalb das Verfahren des (nach den ersten Quellen so genannten) "Chinesischen Restsatzes" noch allgemein an:

Es seien die paarweise teilerfremden Zahlen a₁, a₂,...,a_n gegeben. Um alle Zahlen x mit
xº r₁ mod a₁, xº r₂ mod a₂,...,xº r_n mod a_n zu finden, bestimme man die Zahl a=a₁·a₂·· ·a_n sowie die Zahlen b₁:=a/a₁, b₂:=a/a₂,...,b_n:=a/a_n. Dann bestimme man die Zahlen x_i in den Gleichungen x_i·b_i+y_i·a_i=1 für i=1,...,n. Dann gilt: x_k=x₁·b₁· r₁+...+x_n·b_n·r_n+k·a.

Wir kommen auf das Thema "Chinesischer Restsatz" an späterer Stelle im Zusammenhang mit Kongruenzen noch einmal zurück.

AUFGABE 2.18
a) Finde x mit: xº1 mod 2; xº 2 mod 3; xº3 mod 5; xº4 mod 7; xº5 mod 11; xº6 mod 13
b) ebenso: xº3 mod 11; xº 8 mod 13; xº5 mod 17; xº5 mod 19
c) xº7 mod 11; xº 8 mod 19; xº15 mod 23; xº4 mod 29;
xº5 mod 31

Download Kap_2 (63 KB)

Copyright © Michael Dorner, Dezember 2000.