Lösung zu Kongruenz-System

Question

Aufgabe: Meine Aufgabe ist es dieses Kongruenz-System zu lösen.

X =2 mod 3

X= 4 mod 7

X=6 mod 8

Problem/Ansatz:

Ich habe 1142 mod 168 = 134 rausbekommen. Das stimmt jetzt aber mit der Probe bei 134 = 4 mod 7 nicht. Ich habe bereits eine Antwort bekommen bei dem kommt 158 als Lösung raus.

Ich finde meinen Fehler aber nicht. Ich hoffe es kann mir jemand weiterhelfen.

Comments

Vom Duplikat:

Titel: Probe zum chinesischen Restsatz

Stichworte: konvergenz

Aufgabe:

Hallo, ich habe eine Aufgabe diese lautet:

x= 2 mod  3

x = 4 mod 7

x = 6 mod 8

Kongruenzsystem lösen
Problem/Ansatz:

Ich habe bereits alles ausgerechnet und wollte jetzt nur nachfragen ob ich es auch richtig geschrieben habe.

x1 = 2, x2 = 3, x3 = 5

X = 1142

Dann habe ich geschrieben:

1142 mod 168 = 134. Das ist eine Lösung ist aber auch die kleinste positive Lösung

Ich habe auch die Probe gerechnet:

134 = 2 mod 3  => 134/3=44*3=132+2=134

134 = 4 mod 7  => 134-4=130/7=18*7 =126+4=130

134 = 6 mod 8 => 134-6=128/8=16*8=128+6=134

Bei der Probe bin ich mir nicht ganz sicher ob das so stimmt. Würde mich freuen wenn mir jemand weiterhilft.

Answer 1

Macht es dich nicht stutzig, dass für 134 die Probe mod 7 nicht stimmt?

Eine richtige Lösung ist 158.

Comments

Danke, aber wie sind sie auf 158 gekommen?  Denn groß M ist bei mir 168

M1 ist = 56, M2 = 24 und M3 = 21

X ist dan:

2*56*2 +3*24*4 +5*21*6 = 1142

Dann habe ich den ggT(1142/168) ausgerechnet der ist 2. Und dann den Euklidischen Algorithmus. Da kommt bei mir nichts mit 158 wo liegt da der Fehler?

Answer 2

Wegen der ersten Kongruenz gilt x=3k+2.

Wegen der zweiten Kongruenz gilt x=7m+4.

Wegen der dritten Kongruenz gilt x=8n+6
(x, k, m, n und alle später noch auftauchenden Variablen sollen ganzzahlig sein.)

Aus 3k+2=7m+4 folgt 3k=7m+2, also muss 7m+2 durch 3 teilbar sein.

Das gilt für alle m, die bei Teilung durch 3 der Rest 1 lassen.

Also gilt m=3q+1, 7m=21q+7,  x= (7m+4=) 21q+11.

Jetzt muss du nur noch das System der beiden Gleichungen

x=21q+11

x=8n+6

ganzzahlig lösen. Da kommst du über 8n=21q+5 darauf, dass 21q +5≡0 mod 8 sein muss, was für q=-1 und damit auch für q=7erfüllt ist.

Es gilt also q=8p+7, Wenn du das verwendest, um q in x=21q+11 zu ersetzen, bekommst du

x=21(8p+7)+11=168p + 158.