Chinesischer Restsatz
- Autor:
- Georg Wengler
Lösung eines Systems von Restgleichungen.
z.B.
Welche Zahl eergibt bei Division durch 5 den Rest 1,
bei Division durch 7 den Rest 3, bei Division durch 11 den Rest 5?
m1=5, m2=7, m3=11 mit r1=1, r2=3, r3=5
M = m1*m2*m3 = 385 => c1=M/m1=77, c2=M/m2=55, c3=M/m3=35
=> Löse zunächst: 77y=1 (5), 55y=1 (7), 35y=1 (11)
=> y1=3 (5), y2=6 (7), y3=6(11)
=> Lösung: x = r1*y1*c1+r2*y2*c2+r3*y3*c3 (M)
=> x = 1*3*77 + 3*6*55 + 5*6*35 (385) = 2271 (385) = 346 (385)
d.h. 346 liefert Rest 1 bei Teilung durch 5, Rest 3 bei Teilung durch 7
und Rest 5 bei Teilung durch 11.