Euklidischer Algorithmus (Z)/19 und 109/Chinesischer Restsatz/Aufgabe/Lösung

a) Es ist

{}109=5\cdot 19+14\,,

{}19=1\cdot 14+5\,,

{}5=1\cdot 4+1\,.

Somit ist

{}{\begin{aligned}1&=5-1\cdot 4\\&=5-1\cdot {\left(14-2\cdot 5\right)}\\&=3\cdot 5-1\cdot 14\\&=3\cdot {\left(19-1\cdot 14\right)}-1\cdot 14\\&=3\cdot 19-4\cdot 14\\&=3\cdot 19-4{\left(109-5\cdot 19\right)}\\&=23\cdot 19-4\cdot 109.\end{aligned}}

b) Aufgrund von Teil a) haben wir die Darstellung

{}1-23\cdot 19=-4\cdot 109=-436=1635\,.

Diese Zahl hat modulo ${}19$ den Rest ${}1$ und modulo ${}109$ den Rest ${}0$ , d.h. ${}1635$ entspricht dem Restepaar ${}(1,0)$ .

Aufgrund von Teil a) haben wir die Darstellung

{}23\cdot 19=4\cdot 109+1=437\,.

Diese Zahl hat modulo ${}19$ den Rest ${}0$ und modulo ${}109$ den Rest ${}1$ , d.h. ${}437$ entspricht dem Restepaar ${}(0,1)$ .

c) Es ist

{}(5,10)=5\cdot (1,0)+10\cdot (0,1)=5\cdot 1635+10\cdot 437=8175+4370=12545=119\,.