Berechnen der kleinsten Zahl x mit Kongruenzen

Neue Frage »

Quad84 Auf diesen Beitrag antworten »
Berechnen der kleinsten Zahl x mit Kongruenzen
Meine Frage:
Ich brauche mal wieder eure Hilfe bei folgender Aufgabe:

Berechne die kleinste Zahl x aus nat. Zahlen mit

x kongruent 3 mod 5

x kongruent 2 mod 6

x kongruent 4 mod 7

x kongruent 0 mod 8

Meine Ideen:
Zuerst dachte ich an den Chinesischen Restsatz, aber das geht hier ja nicht, da die Elemente nicht paarweise teilerfremd sind. Also habe ich mich am euklidischen Algorithmus versucht, bekomme da aber nicht wirklich was raus.
Hat jemand eine Idee und könnte mir den Ansatz schreiben?
Ich wäre ser dankbar!!!
ollie3 Auf diesen Beitrag antworten »
RE: Berechnen der kleinsten Zahl x mit Kongruenzen
hallo quad84,
selbstverständlich ist auch das ein fall für den chinesischen restesatz, ich verweise dabei auf die
entsprechende seite bei wikipedia, da werden solche aufgaben ausführlich erklärt, und auch das
die modulen nicht alle teilerfremd sind ist kein hinderungsgrund.
gruss ollie3
tmo Auf diesen Beitrag antworten »

Da gibt es mehrere Möglichkeiten:

Entweder du fasst die Kongruenzen und zu zusammen und wendest dann den chin. Restsatz an.

Oder du wendest zuerst den chin. Restsatz nur auf die Kongruenzen modulo 5,6,7 an und erhältst dann eine Lösung s.
Danach löst du die Kongruenz für t und nimmst natürlich die kleinste Lösung für t.
Quad84 Auf diesen Beitrag antworten »

vielen dank für die schnellen antworten!
ich werde es gleich mal ausprobieren und meine lösung später hier ggf posten!
Quad84 Auf diesen Beitrag antworten »

Hier meine vorläufige Lösungsskizze. Wäre toll, wenn ihr kurz drüber schauen könntet!

Zuerst habe ich den Chin. Rests. für mod 5,6 7 angewendet:
Dann ist M = 210.

M1 = 24
M2 = 35
M3 = 30

Mit Hilfe des erweiterten eukl. Alg. berechne ich nun:

17 * 5 + (-2)*24 = 1 --> e1 = -84

6 * 6 + (-1)*35 = 1 --> e2 = -35

17*7 + (-4)*30 = 1 --> e3 == -120

Damit ergibt sich für das Element s:

s = 3*(-84) + 2 *(-35) + 4 (-120) = -802

Eingesetzt in die Gleichung: s + t * 210 kongruent 0 mod 8 ergibt

210*t kongruent 168420 mod 8

Mit euklidischen Alg den ggt (219,8) berechnet, ergibt wiederum für t = 2.

Also müsste das kleinste Element X = 2 sein.

Ob das so stimmt?????
ollie3 Auf diesen Beitrag antworten »

hallo quad,
also das kann ja überhaupt nicht sein, X=2 erfüllt ja fast garkeine der bedingungen, 2 ist zum beispiel nicht gleich 3 modulo 5, du hast wahrscheinlich
mehrere sachen falsch gemacht, werde das mal durchgehen. verwirrt
gruss ollie3
 
 
Quad84 Auf diesen Beitrag antworten »

Ok neuer Versuch ;-)

Ich habe also laut 1. Vorschlag von euch 2 Kongruenzen zusammengefasst und somit folgendes System zum Lösen benutzt:

x = 8 mod 24
x = 3 mod 5
x = 4 mod 7

Das = steht hierbei für Kongruenz!!!

Nun ergibt sich für M = 840

M1: 35
M2: 168
M3: 120

Dann komme ich auf x gleich - 1688.

Was meint ihr?
tmo Auf diesen Beitrag antworten »

Wenn M = 840 ist, so muss deine Lösung doch am Ende auch zwischen 1 und 840 liegen. Alles andere macht keinen Sinn.

Wir machen mal ein Beispiel:

x = 1 mod 5
x = 2 mod 3
x = 6 mod 10

Es sind nicht alle Modulo teilerfremd, also verwenden wir mal meine zweite Variante.

Der chin. Restsatz liefert für die ersten beiden Kongruenzen:

x = 11 mod 15

Also sind alle Lösungen für die ersten 2 Kongruenzen gegeben durch: mit

Dies setzen wir in die 3te Kongruenz ein und erhalten:

11+15t = 6 mod 10

Umgeformt ergibt sich:
5t = 5 mod 10

Die kleinste positive Lösung ist offensichtlich t = 1.

Also erhalten wir als kleinste Lösung für das gesamte System: 11+15*1 = 26
Quad84 Auf diesen Beitrag antworten »

Könntest du mir diesen Schritt noch einmal ausführlich erklären? Ich verstehe nämlich nicht, wie du auf die Umformung kommst:

"Dies setzen wir in die 3te Kongruenz ein und erhalten:

11+15t = 6 mod 10

Umgeformt ergibt sich:
5t = 5 mod 10"

Das wäre wirklich super ;-)
tmo Auf diesen Beitrag antworten »

11 ist dasselbe wie 1 und 15 dasselbe wie 5 mod 10.

Dann habe ich die 1 auf die andere Seite gebracht und dann stehts auch schon da.
Quad84 Auf diesen Beitrag antworten »

Ok, danke!

Wenn ich das Ganze jetzt mal nachrechne, dann habe ich leider noch ein Problem mit:

"Der chin. Restsatz liefert für die ersten beiden Kongruenzen:

x = 11 mod 15"

Ich komme einfach nicht auf die 11. Was mache ich da falsch???
tmo Auf diesen Beitrag antworten »

Auf was kommst du denn?
Quad84 Auf diesen Beitrag antworten »

Ich komme auf -33.
tmo Auf diesen Beitrag antworten »

Das ist falsch. Dann machst du was generelles beim Algorithmus des chin. Restsatz falsch. Guck ihn dir nochmal genau an und versuche es erneut.

Du solltest auf jeden Fall auf ein Ergebnis kommen, was bei Division durch 15 den Rest 11 lässt. Z.b. 41 wäre auch ok.
Quad84 Auf diesen Beitrag antworten »

Ok, ich schreibe dir einfach mal hin, was ich gerechnet habe zu deiner Beispielaufgabe:

x = 1 mod 5
x = 2 mod 3

Daraus folgt, dass M = 15.
M1: 15/5 = 3
M2: 15/3 = 5

Also: 4*1 + (-1)*3 = 1 --> E1=-3
8*2 * (-3)*5=1 --> E2 = -15

Für s ergibt sich dann: s= (-3) +(-30) = -33

Mein Fehler wird wohl in der Rechnung stecken. Wie bist du denn auf 11 gekommen?
tmo Auf diesen Beitrag antworten »

Was rechnest du denn da?

Die Rechnung sähe doch eher so aus:

(-3)*3+2*5=1

also E1 = -9, E2 = 10

Damit hat man nämlich folgendes erreicht:

E1 = 0 mod 3 und E1 = 1 mod 5
E2 = 0 mod 5 und E2 = 1 mod 3

Und dann kann man daraus die Lösung basteln und es ergibt sich s = -9 + 2*10 = 11
Quad84 Auf diesen Beitrag antworten »

wenn du mir jetzt noch sagst, wo die 2 hier herkommt, dann hast du ne medaillie für deine geduld mit mir verdient!!!!! :-)

s = -9 + 2*10 = 11
Quad84 Auf diesen Beitrag antworten »

ich glaube, ich habs grad selbst herausgefunden:

die 2 stammt ja vom x2!

vielen lieben dank für die hilfe!!!!!!
Quad84 Auf diesen Beitrag antworten »

Kann jemand bitte überprüfen, ob meine Lösung richtig ist? Das wäre wirklich super!



Die Moduln 5,6,7 sind paarweise teilerfremd, sodass der Chin. Restsatz hier gilt. Mit dem Lemma von Bezout ergibt sich:



Mit dem erw. eukl Alg berechnen sich daher für das jeweilige teilerfremde Paar:



Dann muss ich nur noch t bestimmen, welches dann das kleinste x für alle Gleichungen ist.

-178 + t*210 = 0 mod 8

Wie bekomme ich denn nun dieses t?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »