Die mit dem Problem überlieferte Regel ist ein Rezept, keine Suche. Nehmen Sie die drei Reste 2, 3, 2 und multiplizieren Sie sie mit 70, 21 und 15 – Zahlen, die so gewählt sind, dass 70 ≡ 1 (mod 3) und 0 für die anderen ist, 21 ≡ 1 (mod 5), 15 ≡ 1 (mod 7). Der Rechner addiert 70·2 + 21·3 + 15·2 zu 233; subtrahieren Sie zweimal 3·5·7 = 105, und 23 bleibt übrig, die kleinste Antwort. Prüfen Sie es rückwärts: 23 mod 3 ist 2, 23 mod 5 ist 3, 23 mod 7 ist 2.
Der Satz sagt, dass das System genau eine Lösung modulo dem Produkt teilerfremder Moduln hat, 23 ist also die einzige Antwort zwischen 0 und 104, und jede andere Lösung ist 23 + 105k. Die Konstruktion verallgemeinert sich auf beliebig viele Kongruenzen, und dieselbe Algebra taucht weit entfernt von der Arithmetik auf: Es ist der chinesische Restsatz-Isomorphismus Z/105 → Z/3 × Z/5 × Z/7, der Grund, warum man eine Zahl gegen mehrere kleine Moduln zugleich hashen kann, und das Rückgrat des expliziten Rekonstruktionsschritts in der Arithmetik mit Restzahlensystemen, die zum exakten Summieren benutzt wird.
Antwort
23
So lesen Sie sie
233 mod 105 auf dem Rechner. Der erste Link baut 233 aus den Koeffizienten 70, 21 und 15 der Versregel; der dritte zeigt den ersten der drei Reste, 2.
Quelle
Sunzi suanjing (Master Sun's Mathematical Manual, c. 400 CE) poses the problem 'there is an unknown number, divided by 3 it leaves 2, divided by 5 it leaves 3, divided by 7 it leaves 2'; the general constructive rule appears in Qin Jiushao's Shushu Jiuzhang of 1247, and the theorem in its modern form belongs to Euler's work on congruences before Gauss put it in the Disquisitiones Arithmeticae of 1801 — which is why the theorem is called Chinese in the West
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.