Wieso ist der chinesische Restsatz hier anwendbar?
Ich weiß was er besagt, simultane Kongurenz lässt sich damit berechnen, also
Für eindeutige Lösung zw. 0 und m_1 * ... * m_n = M sind m_1, ..., m_n paarweise teilerfremd
Wenn ich z. B. diese Aufgabe habe:
2^1000 mod 1155
Dann steht bei uns im Skript, gut, wir machen Primfaktoren 1155 = 3 * 5 * 7 * 11
berechnen jeweils den Modulo 2^1000 mod 3 = ?, ....,
und das ist dann unser a_1, a_2, ...
Und x dann die Lösung der Ursprungsfrage. Aber warum funktioniert das so? Sehe nicht wieso der Restsatz hier überhaupt anwendbar ist, wie kann man das zeigen?
1 Antwort
Du berechnest
2^1000 = a1 mod 3
2^1000 = a2 mod 5
2^1000 = a3 mod 7
2^1000 = a4 mod 11
Mit dem chinesischen Restsatz sucht man dann ein x, so dass
x = a1 mod 3
x = a2 mod 5
x = a3 mod 7
x = a4 mod 11
Für dieses x gilt dann x = 2^1000 mod 1155, denn die Lösung ist mod 1155 eindeutig, und das ist das, was gesucht war.