Simultane Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:51 So 17.02.2013 | | Autor: | fl0nk |
| Aufgabe | Lösen Sie das folgende System simultaner Kongruenzen:
x=1 mod 108
x=13 mod 40
x=28 mod 225 |
Mein Problem liegt darin, dass die Moduln nicht teilerfremd sind.
Ich habe die einzelnen Moduln schon mit PFZ aufgedröselt und komme dadurch auf das etwas längere System:
x=1 mod 4
x=1 mod 27
x=13 mod 8=5 mod 8
x=8 mod 5=3 mod 5
x=28 mod 25=3 mod 25
x=28 mod 9=1 mod 9
Ist das soweit ok? Wenn nein, wo liegt mein Denkfehler?
Falls es ok ist, weiß ich jetzt nicht wie ich weitermachen soll...
Über eure Hilfe würde ich mich sehr freuen.
|
|
| |
|
Hallo,
> Lösen Sie das folgende System simultaner Kongruenzen:
>
> x=1 mod 108
> x=13 mod 40
> x=28 mod 225
> Mein Problem liegt darin, dass die Moduln nicht
> teilerfremd sind.
> Ich habe die einzelnen Moduln schon mit PFZ aufgedröselt
> und komme dadurch auf das etwas längere System:
>
> x=1 mod 4
> x=1 mod 27
> x=13 mod 8=5 mod 8
> x=8 mod 5=3 mod 5
> x=28 mod 25=3 mod 25
> x=28 mod 9=1 mod 9
>
>
> Ist das soweit ok? Wenn nein, wo liegt mein Denkfehler?
Das ist ok so.
Du musst das System nun wieder in eines mit teilerfremden Moduln zusammenfassen (um dann die üblichen Lösungsmethoden anwenden zu können).
Schau dir dazu mal diesen Beitrag hier an, da wurde die Aufgabe schonmal diskutiert.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:18 Mo 18.02.2013 | | Autor: | fl0nk |
Super, danke für deine Antwort.
Das Thema hab ich nicht entdeckt.
Habs jetzt gecheckt (auch wenn die Zahlen doch recht groß wurden^^), aber zur Sicherheit:
Ich zerlege alle Moduln in Primfaktoren.
Danach suche ich mir zu jedem Primfaktor die höchste vorkommende Potenz.
Die jeweilige Gleichung wird dann ins neue System übernommen.
Dann sind alle Moduln teilerfremd und ich kann den Algorithmus nach dem chin. Restsatz anwenden.
Passt das so?
|
|
|
| |
|
Hallo fl0nk,
> Super, danke für deine Antwort.
> Das Thema hab ich nicht entdeckt.
> Habs jetzt gecheckt (auch wenn die Zahlen doch recht groß
> wurden^^),
Das wird Dir in der Zahlentheorie häufiger passieren. Große Zahlen sind halt auch nicht anders als kleine. Und überhaupt ist ja alles relativ. Zum Beispiel ist es jetzt schon relativ spät... 
> aber zur Sicherheit:
>
> Ich zerlege alle Moduln in Primfaktoren.
> Danach suche ich mir zu jedem Primfaktor die höchste
> vorkommende Potenz.
> Die jeweilige Gleichung wird dann ins neue System
> übernommen.
> Dann sind alle Moduln teilerfremd und ich kann den
> Algorithmus nach dem chin. Restsatz anwenden.
>
> Passt das so?
Ja, so passt das perfekt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:50 Mo 18.02.2013 | | Autor: | fl0nk |
Ok, danke für die Hilfe.
Nur sind die Zahlen wohl doch etwas groß für ne Klausuraufgabe, wenn man keinen Taschenrechner nutzen darf ;)
Stecke da grade in den Vorbereitungen^^
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:07 Mo 18.02.2013 | | Autor: | reverend |
Hallo nochmal,
> Ok, danke für die Hilfe.
> Nur sind die Zahlen wohl doch etwas groß für ne
> Klausuraufgabe, wenn man keinen Taschenrechner nutzen darf
> ;)
>
> Stecke da grade in den Vorbereitungen^^
In der Klausur kommt es vor allem darauf an, dass Du die Besonderheit der Aufgabe erkennst und dafür einen Lösungsweg anbieten kannst.
Und wenn ich nicht irre, ist die größte benötigte Zahl 8*25*27=5400. Das geht doch noch?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:21 Mo 18.02.2013 | | Autor: | fl0nk |
Ja, das geht noch, das Problem ist nachher nur 1 als Produkt der jeweiligen n und n "hut" darzustellen ;)
Aber mal noch ne andere Frage:
Bon gerade auf ein System mit
mod 6 und mod 10 gestoßen.
Hier ist ja das Problem, dass 2 in beiden PFZ als höchste Potenz vorkommt.
Wie gehe ich dann vor?
|
|
|
| |
|
Hallo nochmal,
> Ja, das geht noch, das Problem ist nachher nur 1 als
> Produkt der jeweiligen n und n "hut" darzustellen ;)
Ja, ok. Das kann mühsamer werden...
> Aber mal noch ne andere Frage:
> Bon gerade auf ein System mit
> mod 6 und mod 10 gestoßen.
> Hier ist ja das Problem, dass 2 in beiden PFZ als höchste
> Potenz vorkommt.
> Wie gehe ich dann vor?
Na, auch hier: zerlegen in Kongruenzen [mm] \mod{2}, \mod{3}, \mod{5}.
[/mm]
Die in beiden vorliegenden Kongruenzen enthaltene Aussage [mm] \mod{2} [/mm] darf sich natürlich nicht widersprechen:
[mm] x\equiv 3\mod{6}\;\;\wedge\;\; x\equiv 4\mod{10} [/mm] ist nicht lösbar.
[mm] x\equiv 5\mod{6}\;\;\wedge\;\; x\equiv 7\mod{10} [/mm] dagegen ließe sich reduzieren auf:
[mm] x\equiv 2\mod{3}\;\;\wedge\;\; x\equiv 7\mod{10}
[/mm]
...womit ein zweiter Weg angedeutet ist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:31 Mo 18.02.2013 | | Autor: | fl0nk |
Das ist soweit klar, allerdings habe ich nen Parameter im System, der mich doch sehr verwirrt.
Hier mal das System:
3x=a mod 6
7x=1 mod 10
Hier muss ich ja eigentlich erst den Parameter bestimmen und wie das gehen soll, weiß ich nicht so recht...
|
|
|
| |
|
Hallo nochmal,
> Das ist soweit klar, allerdings habe ich nen Parameter im
> System, der mich doch sehr verwirrt.
>
> Hier mal das System:
> 3x=a mod 6
> 7x=1 mod 10
>
> Hier muss ich ja eigentlich erst den Parameter bestimmen
> und wie das gehen soll, weiß ich nicht so recht...
Es gibt doch nur zwei mögliche Werte für a, nämlich 0 und 3.
Damit ist dann klar, ob x gerade oder ungerade ist.
Aus der zweiten Kongruenz folgt dann, dass nur ein einziger Wert für a möglich ist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:14 Mo 18.02.2013 | | Autor: | fl0nk |
Ok, dass a= 0 oder 3 folgt ist mir jetzt klar, da ja vielfache von 3 entweder Rest 3 mod 6 haben oder eben auch Vielfache von 6 sind, also 0 mod 6.
Aber warum ergibt sich aus der zweiten Gleichung der tatsächliche Wert von a?
Ich kann die Gleichung zerlegen in
7x=1 mod 5
7x=1 mod 2
Wie geh ich jetzt weiter vor?
|
|
|
| |
|
Hallo,
> Ok, dass a= 0 oder 3 folgt ist mir jetzt klar, da ja
> vielfache von 3 entweder Rest 3 mod 6 haben oder eben auch
> Vielfache von 6 sind, also 0 mod 6.
Wenn a=0 ist, ist x gerade, also [mm] x\equiv 0\mod{2}.
[/mm]
Wenn a=3 ist, ist x ungerade, also [mm] x\equiv 1\mod{2}.
[/mm]
> Aber warum ergibt sich aus der zweiten Gleichung der
> tatsächliche Wert von a?
>
> Ich kann die Gleichung zerlegen in
>
> 7x=1 mod 5
Hieraus folgt [mm] x\equiv 3\mod{5}.
[/mm]
> 7x=1 mod 2
Hieraus folgt [mm] x\equiv 1\mod{2}.
[/mm]
Und hier lohnt es sich, nochmal einen Blick zurück zu werfen...
> Wie geh ich jetzt weiter vor?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:25 Mo 18.02.2013 | | Autor: | fl0nk |
Ok, das ist soweit klar, danke :)
Nun bin ich noch auf folgendes gestoßen:
f= 2+3(x-1) mod (x-1)²
f= 1+2(x+1) mod (x+1)²
Soweit so gut, wenn mich nicht alles täuscht, sind die Moduln ja teilerfremd.
Allerdings schaff ich es jetzt nicht, bei Anwendung des chin. Restsatzes
1 als m(x-1)²+n(x+1)² zu schreiben.
Siehst du da auf die schnelle was?
Oder muss ich hier anders vorgehen, d.h. gibt nen Trick den ich mal wieder übersehe?
|
|
|
| |
|
Hallo nochmal,
> Ok, das ist soweit klar, danke :)
Freut mich.
> Nun bin ich noch auf folgendes gestoßen:
Das ist eine neue Aufgabe; ich verlege die daher gleich mal innerhalb des Threads. Das ist hoffentlich ok.
> f= 2+3(x-1) mod (x-1)²
> f= 1+2(x+1) mod (x+1)²
>
> Soweit so gut, wenn mich nicht alles täuscht, sind die
> Moduln ja teilerfremd.
Für ungerade x sind sie das nicht.
Für gerade x sind sie für x>2; ich würde sogar vermuten, dass dies die eigentliche Aufgabe ist. Gibt es eine solche Angabe?
> Allerdings schaff ich es jetzt nicht, bei Anwendung des
> chin. Restsatzes
> 1 als m(x-1)²+n(x+1)² zu schreiben.
Dafür brauchst Du ja auch den erweiterten euklidischen Algorithmus.
Zugegeben, ohne den klappt die Auflösung des chinesischen Restsatzes auch nicht.
> Siehst du da auf die schnelle was?
Ehrlich gesagt: nein.
> Oder muss ich hier anders vorgehen, d.h. gibt nen Trick
> den ich mal wieder übersehe?
Nehmen wir mal x gerade und x>2 an, so dass [mm] \ggT{((x-1)^2,(x+1)^2)}=1 [/mm] ist.
Euklid, nicht erweitert (also klassisch):
[mm] (x^2+2x+1):(x^2-2x+1)=1\;\;\; \text{Rest}\;\;4x
[/mm]
[mm] (x^2-2x+1):4x=\bruch{1}{4}x\;\;\; \text{Rest}\;\;-2x+1
[/mm]
[mm] 4x:-2x+1=-2\;\;\;\text{Rest}\;\;2
[/mm]
[mm] -2x+1:2=-x\;\;\;\text{Rest}\;\;1
[/mm]
[mm] -x:1=-x\;\;\;\text{Rest}\;\;0
[/mm]
Jetzt schreib den mal um in die moderne, sogenannte erweiterte Variante.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 18:05 Di 19.02.2013 | | Autor: | fl0nk |
Hmm...
Ich rechne jetz schon ne gefühlte Ewigkeit rum, aber irgendwie sieht das bei mir total chaotisch aus und ich kann selten mal was zusammenfassen...
Und wenn ich mal was rausbekomme, ist es falsch, da die Summe von
a(x+1)²+b(x-1)² nie 1 wird bei meinen Ergebnissen...
Edit: Habe mal unten meine Rechung angehängt.
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Do 21.02.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
