Hallo,
also, ich erkläre dir, wie ich es verstanden habe. Es geht also um mod 77 mod 12
Wenn der ersten Kongruenz genügt, dann gibt es ein , sodass . Wenn der zweiten Kongruenz genügt, dann gibt es ein , sodass .
Also muss (I) gelten. Nun finden wir erst einmal so ein Paar , das sowas leistet. So etwas gibt es nur, wenn der ein Teiler von ist, was aber hier der Fall ist. Wir bedienen uns des euklidischen Algorithmus:
(<- diese Zeile brauchen wir eigentlich nicht)
Gut, also ist der (was man vom Hinsehen her hätte sagen können). Wir brauchen die Rückwärtseinsetzung, um aus 1 eine -Linearkombination aus 12 und 77 zu machen:
Vorletzte Zeile =>
Also schreibe ich (I) wie folgt:
Umformen ergibt: bzw. (II)
All die Arbeit, nur um (II) zu erhalten. Da nämlich 77 kein Teiler von 12 ist, muss es also ein Teiler von sein. Umgekehrt muss 12 (was 77 nicht teilt) einer von sein.
Der Einfachheit halber kann man und setzen. (Probe: einerseits und andererseits.
So, damit ist eine Partikulärlösung gefunden, nämlich (eine kleinere wäre auch möglich gewesen, aber ich rechne eben so). Nun überlegen wir uns, welches noch alles Lösungen sind. Geht man nun gleichzeitig in 77er Schritten UND(!) in 12er Schritten (also in er Schritten), dann treffen wir natürlich wieder auf so eine Lösung, etwa . Also sind schonmal alle mit mod 924 Lösungen. Dass es keine anderen Lösungen außerhalb dieser Schrittreichweite (924) geben kann, kann man leicht damit beweisen, dass tatsächlich die kleinste natürliche Lösung darstellt. Gäbe es noch andere, kann man leicht einen Widerspruch zu dieser Tatsache konstruieren. (Details im Beweis zum chinesischen Restsatz)
Mfg Michael
|