Modulo

Neue Frage »

Leo1234 Auf diesen Beitrag antworten »
Modulo
Hallo miteinander

Ich habe die Frage, ob es einen Algorithmus (oder "Trick") gibt, um eine Zahl x ( x > 0) zu finden, sodass zB gilt:
x = 1 (mod 4) UND x = 2 (mod 5).

Die Lösung ist mir bekannt, allerdings durch reines probieren - daher meine Frage.

Liebe Grüsse,
Leo
galoisseinbruder Auf diesen Beitrag antworten »

Wikipedia erklärts ganz gut.
Leo1234 Auf diesen Beitrag antworten »

Ah cool, danke!

Ein anderes Problem stellt sich noch bei Polynomen:
Ich kenne:
f = (x-5) (mod (x-5)^2)
f = 3 (mod x-1)
f = 1 + 2(x+10) (mod (x+10)^3)

Hier hab ich wieder M (vrgl. wiki) = (x-5)^2 (x-1) (x+10)^3 und die M_i.
Dann zum euklid. Algo:
_______ * (x-5)^2 + _____ *(x-1)(x+10)^3 = 1.
Die Lücken zu füllen ist hier einiges schwieriger. Gibt's hierzu auch einen "Trick", oder kommt man nicht ums Probieren herum?
galoisseinbruder Auf diesen Beitrag antworten »

Wie im Artikel daneben bzw. drüber steht verwendet man dafür den erweiterten euklidischen Algorithmus. Was geschickteres ist mir nicht bekannt.
Leo1234 Auf diesen Beitrag antworten »

Aber dafür muss man ja schon eine Vorahnung haben, wie das Gleichungssystem zu lösen ist. ..allerdings kenn ich weder das erste noch das zweite Produkt.
galoisseinbruder Auf diesen Beitrag antworten »

Nein. Du berechnest den ggT von und und mittels dem Vorgehen dass man erweiterter euklidischer Algorithmus nennt erhälst du zwei Polynome f,g mit .

P.S. Hatten wir zwei nicht schonmal ´ne Aufgabe mit dem EEA?
 
 
Leo1234 Auf diesen Beitrag antworten »

Okey, der ggT ist 1.
..wie ich dann aber auf f, g kommen soll, ist mir noch nicht klar.

PS: ..doch Augenzwinkern
galoisseinbruder Auf diesen Beitrag antworten »

Dann ist es jetzt an der Zeit (oder schon überfällig) sich den EEA genauer anzuschauen.
Mit der boradsuche findest Du hier auch einige Beispiele.
Leo1234 Auf diesen Beitrag antworten »

Also wie der EEA funktioniert ist mir klar. Habe dazu inzwischen auch einige Aufgaben gelöst.
Was mir allerdings noch nicht klar ist: Worauf genau muss ich den EEA anwenden? Auf (x-1)(x+10)^3 / (x-5)^2 ?
galoisseinbruder Auf diesen Beitrag antworten »

Das hatte ich doch schon geschrieben. Polynom 1 ist , Polynom 2 ist .
Du willst ja so eine Darstellung der 1.
Leo1234 Auf diesen Beitrag antworten »

Vielen Dank! ..sorry, das hab ich vorher eben nicht richtig verstanden.
Ich bin eigentlich fertig. Ich habe ja 3 Teilresultate nach dem EEA erhalten. Ist es korrekt, wenn ich diese Resultate per " + " am Schluss zusammengefügt habe?
galoisseinbruder Auf diesen Beitrag antworten »

Beim EEA solltest Du keine Teilresultate erhalten, der Alg. geht durch bis zur gewünschten Darstellung. Wenn Du die Rechnung postest kann ich evtl. nachvollziehen was Du genau meinst.
Leo1234 Auf diesen Beitrag antworten »

Also, ich habe ja 1.)
(x-1)(x+10)^3 = .... (x-5)^2 + 6075x-16875
...
und bekomme dann (400/81) als ggT.

Bei (x-5)^2 * (x+10)^3 bekomme ich 21296 und bei (x-5)^2 * (x-1) ist es (x+10)^3.

Ist das nicht ok so? ..oder muss ich nun noch den ggT dieser drei Teilresultate machen (was eigentlich doch noch logischer wäre..)
ollie3 Auf diesen Beitrag antworten »

hallo leo,
kenn dich natürlich noch, glaube,dass deine ergebnisse leider total falsch sind,
für f und g müssen ja polynome rauskommen und nicht nur zahlen.
Wie hattest du das denn mit dem erw.eukl.algo. gemacht, hattest du die
polynome vorher ausmultipliziert?
gruss ollie3
Leo1234 Auf diesen Beitrag antworten »

Ja, habs so gemacht:
Für den ersten Durchlauf:
(x^4 + 29x^3 + 270x^2 + 700x - 1000) = (x^2 + 39x + 635) * (x-5)^2 + 6075x - 16875
x^2 - 10x + 25 = .... + (400/81)
6075x - 16875 = ... * 400/81 + 0
--> 400/81 wäre meiner Meinung nach die Lösung.

Was habe ich falsch gemacht bzw. wie wäre es korrekt?
Leo1234 Auf diesen Beitrag antworten »

Anmerkung:
Also das wäre eine von drei Teillösungen - aber wenn die schon fehlerhaft ist, dann sind es die anderen auch.
galoisseinbruder Auf diesen Beitrag antworten »

So, bin wieder da.
Was Du ausgerechnet hast ist nur der euklidische Algorithmus.
Und da der ggT nur bis auf Asoziiertheit (Multiplikation mit Einheiten) eindeutg bestimmt ist der ggT(.,.)=1.
Jetzt kommt der EEA ins Spiel: die Gleichungnskette "rückwärts" rechnen für diese Darstellung.

Und die drei Rechnung kommen von den drei polynomen hier
Zitat:
oder?
Leo1234 Auf diesen Beitrag antworten »

Genau.
Was aber meinst du mit "jetzt kommt der EEA ins Spiel"?
Wie der EEA funktioniert, weiss ich eigentlich (gleich wie mit Zahlen nehm ich an, oder?)
galoisseinbruder Auf diesen Beitrag antworten »

Es geht doch noch um diese Frage
Zitat:
Dann zum euklid. Algo: _______ * (x-5)^2 + _____ *(x-1)(x+10)^3 = 1. Die Lücken zu füllen ist hier einiges schwieriger. Gibt's hierzu auch einen "Trick", oder kommt man nicht ums Probieren herum?
.
Das heißt um die Bestimmung der Polynome die ich f,g genannt habe. Und dafür brauchst Du den EEA.
Reden wir hier aneinander vorbei?
Leo1234 Auf diesen Beitrag antworten »

Nein, wir reden vom gleichen Problem Augenzwinkern
..ich weiss jedoch nicht, wo meine Fehler liegen (bzw. wie es richtig sein müsste).
galoisseinbruder Auf diesen Beitrag antworten »

Das Problem ist scheinbar, dass Du den erweiterten euklidichen Algorithmus nicht verstanden hast.
Ich fürs mal an einem kleinen Zahlenbeispiel vor:
ggT(13,31): euklidischer Algorithmus
31=2*13+5
13=2*5+3
5=1*3+2
3=1*2+1
erweiterter Euklid:
1=3-1*2 (Du Zeile drüber nach dem Rest auflösen und einsetzen hier: 2=5-1*3)
1=3-(5-1*3)=2*3-1*5 (2.Zeile nach 3 auflösen 3=13-2*5)
1=2*(13-2*5)-1*5=2*13-5*5 (5=31-2*13)
1=2*13-5*(31-2*13)=12*13-5*31
Funktioniert genauso für Polynome
Neue Frage »
Antworten »



Verwandte Themen

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