Chinesischer Restsatz

Question

Aufgabe:

Bestimmen Sie die kleinste vierstellige Zahl x ∈ ℕ mit
x ≡ 2 mod 4; x ≡ 3 mod 7 und x ≡ 2 mod 11

Problem/Ansatz:

Ich bin der Meinung ich habe die Aufgabe schon zu 95% fertig. Allerdings habe ich ein Problem mit der verlangten Vierstelligkeit:

Geg:

m1 = 4, m2 = 7, m3 = 11

M = m1 * m2 * m3 = 308

M1 = 77, M2 = 44, M3 = 28 mit Mi = M/mi, i ={1,2,3}

r1 * m1 + s1 * M1 = 1 => (-19) * 4 + 1 * 77 = 1 => e1 = 1 * 77 mit ei = si * Mi, i = {1,2,3}

e2 = -132, e3 = 56

jetzt alles zusammenrechnen:

∑xi*ei mit i = {1,2,3}

(-2) * 77 + 3 * (-132) + 2 * 56 = -428

-428 ≡ -120 mod 308

Ersteinmal: Ist das Vorzeichen hier überhaupt relevant für die Kongruenz? x soll ja Element von ℕ sein.

Und: Wie komme ich auf Vierstelligkeit? Soll ich einfach 308 solange addieren bis x vierstellig ist?

Comments

Wolframalpha kommt zur Kontrolle auf

x = 308 k + 178

Wähle jetzt das kleinste k welches eine 4 stellige Zahl ergibt.

mit k = 3 ergibt sich x = 1102

Answer 1

-428 ist mit Sicherheit falsch.

x soll bei Teilung durch 4 den Rest 2 lassen. -428 ist aber durch 4 teilbar.

Wenn du eine richtige Lösung hast, musst du dann tatsächlich nur so lange 308 addieren, bis es vierstellig wird.

Answer 2

Du hast einen Fehler in der Zeile

(-2) * 77 + 3 * (-132) + 2 * 56 = -428

Behebe diesen und du kommst auch auf die richtige Lösung.