Chinesischer Restsatz?
Hey!
Ich bekomme diese Aufgabe immer falsch hin und ich weiß nicht, was ich da falsch tue. Als Antwort bekomme ich 419 (zuletzt), aber das passt nicht. Kann mir jemanden dabei helfen?
3 Antworten
Naja. Dann erzähl doch mal, wie du das probiert hast. Also, wie du zu 419 (zuletzt) gekommen bist. Sonst kann man dir weniger gezielt helfen.
Insbesondere wissen wir auch nicht genau, wie die „Methode aus der Vorlesung“ aussieht, die verwendet werden soll.
Ich kann natürlich vorrechnen, wie ich das rechnen würde. Aber, ob dir das dann hilft... Naja.
============
Zunächst einmal kann man feststellen, dass 3, 5, 34 offensichtlich paarweise teilerfremd sind und miteinander multipliziert 510 ergeben, weshalb man tatsächlich eine eindeutige Lösung in ℤ₅₁₀ erhält.
Übliche Bezeichnungen:
Mit dem erweiterten euklidischen Algorithmus kann man nun jeweils rᵢ und sᵢ mit rᵢ ⋅ mᵢ + sᵢ ⋅ Mᵢ =1 finden. Wichtig ist hier vor allem das Inverse sᵢ von Mᵢ modulo mᵢ, um damit eᵢ = sᵢ ⋅ Mᵢ zu erhalten.
Insbesondere zumindest das Inverse s₃ von M₃ = 15 modulo m₃ = 34 soll laut Aufgabenstellung mit dem erweiterten euklidischen Algorithmus bestimmt werden. [Die anderen darf man auch „erraten“.]
Demnach erhält man s₃ = -9 als ein Inverses von M₃ = 15 modulo m₃ = 34 und damit dann...
Für i = 1 bzw. i = 2 kann man
finden. [Alternativ könnte man beispielsweise auch s₁ = 2 bzw. s₂ = 3 verwenden, wenn man möchte.]
Letztendlich ist dann
eine Lösung des Kongruenzensystems.
Wenn man eine Lösung im Bereich [0; 510[ haben möchte, kann man noch 2 ⋅ 510 dazu addieren und erhält dann 37 als Lösung.
Ergebnis:
Wir suchen nun eine Lösung, die jede Kongruenz erfüllt. Wie können wir hier vorgehen?
Naja, wir können für jede Gleichung eine Lösung angeben, die diese erfüllt aber eingesetzt in die anderen verschwindet. Machen wir das für jede Gleichung und addieren alle drei Lösungen zusammen, haben wir eine Lösung des Systems gefunden (wir nutzen also die Linearität dieses Systems aus).
Überlegen wir uns erstmal, welche Zahlen in allen Gleichungen verschwinden können. Ganz einfach, wenn es Vielfache des kleinsten gemeinsamen Vielfaches (kgV) der Zahlen 3, 5 und 34 sind. Denn kgV(3, 5, 34) = 510 hat per Definition als Teiler 3, 5 und 34. Nennen wir kgV(3, 5, 34) kurz M. Es gilt also
M ≡ 0 (mod 3),
M ≡ 0 (mod 5),
M ≡ 0 (mod 34).
Jetzt suchen wir Zahlen, die nur in genau zwei der Gleichungen verschwinden. Dafür machen wir uns zunutze, dass 3, 5 und 34 teilferfremd zueinander sind, also dass der größte gemeinsame Teiler (ggT) 1 ist, ggT(3, 5, 34) = 1. Was hilft uns das? Dividieren wir M z. B. mit 3 also, M / 3, dann ist
M / 3 ≡ k (mod 3)
mit einer natürlichen Zahl k ≠ 0. Aber weiterhin ist
M / 3 ≡ 0 (mod 5),
M / 3 ≡ 0 (mod 34).
Das gilt aber gerade deswegen, weil ggT(3, 5, 34) = 1 ist. Denn 5 und 34 sind damit keine Vielfache von 3, M / 3 also auch nicht mehr.
Analog kann man das für M / 5 und M / 34 begründen. Bleiben wir aber erstmal bei M / 3. Bis jetzt wissen wir nur, dass
M / 3 ≡ k (mod 3)
mit einer natürlichen Zahl k ≠ 0. Wir wollen aber, dass k = 1 ist. Wir suchen also das multipkliativ inverse Element zu k. Das geht so, indem wir mit dem erweiterten euklidischen Algorithmus Zahlen a und b bestimmen, für die
3 • a + M / 3 • b = 1
ist. Dass geht, weil ja 3 und M / 3 teilferfremd sind. Warum wollen wir das lösen? Naja, wenn wir dass Modulo 3 rechnen, erhalten wir
M / 3 • b ≡ 1 (mod 3).
Das b ist also unser gesuchtes inversen Element. Wenden wir den Algorithmus also an (vergiss nicht, M = 510 => M / 3 = 170):
170 = 3 • 56 + 2
3 = 2 • 1 + 1
1 = 1 • 0 + 1
Wie erwartet, ist der ggT eins. Nun die "Erweiterung":
1 = 3 – 2 • 1
1 = 3 – (170 – 3 • 56)
1 = 3 • 57 + (–1) • 170
Damit ist M / 3 • b = –170. Wir haben eine Zahl gefunden, für die gilt
–170 ≡ 1 (mod 3),
–170 ≡ 0 (mod 5),
–170 ≡ 0 (mod 34).
Analog können wir für die anderen beiden Gleichungen eine solche Zahl finden:
–204 ≡ 0 (mod 3)
–204 ≡ 1 (mod 5)
–204 ≡ 0 (mod 34)
und
–135 ≡ 0 (mod 3)
–135 ≡ 0 (mod 3)
–135 ≡ 1 (mod 34).
Multiplizieren wir nun noch –204 mit 2 und –135 mit 3, haben wir eine Lösung gefunden, nämlich
x = –170 • 1 – 204 • 2 – 135 • 3
x = –983
Um alle Lösungen zu erhalten, müssen wir das Ergebnis noch mit der homogenen Lösung addieren. Die homogene Lösung besteht gerade aus den Vielfachen des kgV(3, 5, 34) = 510, wie du leicht nachrechnen kannst. Also ist die vollständige Lösung
x = –983 + 510 • k
mit einer ganzen Zahl k.
Es ist bei mir schon über 50 Jahre her und möglicherweise interpretiere ich die Darstellung und dadurch die Fragestellung falsch. 510 = 3 * 5 * 34 ,
37 mod 3 = 1 ; 37 mod 5 = 2 ; 37 mod 34 = 3 ;
Nachtrag: x = a*3 +1 ; x = b*5 + 2 ; x = c*34 + 3 ;
Also die Aufgabestellung ist mir bisschen irritierend, aber normalerweise berechnet man hier das x, was Sie richtig gemacht haben. Wie sind Sie darauf gekommen? Bei mir kam einmal diese Antwort raus, aber ich glaube da war ich so schnell, sodass ich es übersehen habe. Ich habe aber den erweiterten eukl. Alg. benutzt und daraus y=1 für alle Zahlen bekommen, dann 1×170+2×102+3×45=419. Also Regeln benutzt aber falsches Ergebnis.