simultane lineare kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:53 Fr 14.01.2011 | | Autor: | Bodo0686 |
| Aufgabe | | Löse die simultane lineare Kongruenz |
3X [mm] \equiv [/mm] 3 mod 4
4X [mm] \equiv [/mm] 1 mod 5
8X [mm] \equiv [/mm] 5 mod 11
Jetzt muss ich doch zuerst alles auf die Form
[mm] aX\equiv [/mm] c mod m bringen, oder? Also dass nur das X alleine steht?
Aber wie stelle ich dass nun an?
Bitte um Hilfe. Hier hackt es ganz gewaltig bei mir...
Grüße
|
|
| |
|
Hallo Bodo0686,
> Löse die simultane lineare Kongruenz
> 3X [mm]\equiv[/mm] 3 mod 4
> 4X [mm]\equiv[/mm] 1 mod 5
> 8X [mm]\equiv[/mm] 5 mod 11
>
> Jetzt muss ich doch zuerst alles auf die Form
>
> [mm]aX\equiv[/mm] c mod m bringen, oder? Also dass nur das X alleine
> steht?
> Aber wie stelle ich dass nun an?
Berechne die multiplikativen Inversen
bezüglich des entsprechenden Moduls.
Berechne demnach die multiplikative Inverse von
- 3 bezüglich des Moduls 4
- 4 bezüglich des Moduls 5
- 8 bezüglich des Moduls 11
Das machst Du mit dem ![[]](/images/popup.gif) erweiterten euklidischen Algorithmus.
> Bitte um Hilfe. Hier hackt es ganz gewaltig bei mir...
>
> Grüße
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:36 Sa 15.01.2011 | | Autor: | Bodo0686 |
Hallo,
machen wir das mal für den ersten Fall:
[mm] 3X\equiv [/mm] 3 mod 4
Euklidischer Algor. auf (3,4)
4=1*3 Rest 1
3=3*1 Rest 0
und nun?
Grüße
|
|
|
| |
|
Hallo Bodo,
> Hallo,
>
> machen wir das mal für den ersten Fall:
>
> [mm]3X\equiv[/mm] 3 mod 4
>
> Euklidischer Algor. auf (3,4)
>
> 4=1*3 Rest 1
> 3=3*1 Rest 0 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> und nun?
Rückwärtseinsetzen:
[mm]\operatorname{ggT}(4,3)=1=4-1\cdot{}3[/mm]
Aber hier sieht man doch direkt, dass [mm]X=1[/mm] Lösung ist.
Du kannst doch wegen [mm]\operatorname{ggT}(4,3)=1[/mm] bedenken- und gefahrlos durch 3 kürzen und bekommst:
[mm]X \ \equiv \ 1 \ \ \operatorname{mod}(4)[/mm]
>
> Grüße
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:28 Sa 15.01.2011 | | Autor: | Bodo0686 |
Hallo,
ok!
Aber wie sieht es denn mit 4X [mm] \equiv [/mm] 1 mod 5 aus?
ggt(5,4)=1
-> X [mm] \equiv [/mm] 1 mod 5 (wenn ja Rest 1 dort steht, dann ist dies ja auch für "aX" gegeben, richtig? Bzw. der Rest des eukl. Algor. stimmt mit dem ggT überein...
Nun aber zu 8X [mm] \equiv [/mm] 5 mod 11
ggT(11,8)=1 aber mit was kann ich denn hier kürzen?
Grüße
|
|
|
| |
|
Hallo Bodo,
mit den Kongruenzen tust Du Dich aber immer noch schwer...
> Aber wie sieht es denn mit 4X [mm]\equiv[/mm] 1 mod 5 aus?
> ggt(5,4)=1
>
> -> X [mm]\equiv[/mm] 1 mod 5 (wenn ja Rest 1 dort steht, dann ist
> dies ja auch für "aX" gegeben, richtig? Bzw. der Rest des
> eukl. Algor. stimmt mit dem ggT überein...
Das ist wahrscheinlich nur kraus formuliert, aber ich verstehe es jedenfalls nicht. Da $ [mm] 4\equiv -1\mod{5} [/mm] $ ist, "sieht" man die Lösung $ [mm] X\equiv -1\equiv 4\mod{5} [/mm] $ aber auch ohne erw.euklid.Algo....
> Nun aber zu 8X [mm]\equiv[/mm] 5 mod 11
> ggT(11,8)=1 aber mit was kann ich denn hier kürzen?
Hier ist nichts zu kürzen. Entweder Du kommst darauf, dass auch $ [mm] 16\equiv 5\mod{11} [/mm] $ ist - und dann kannst Du kürzen, oder Du gehst eben den Algorithmus durch; besonders lang ist er ja hier nicht.
Hatte zur ganzen Aufgabe eigentlich schon jemand den Begriff "Chinesischer Rest(e)satz" in die Runde geworfen?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:10 Sa 15.01.2011 | | Autor: | Bodo0686 |
> Hallo Bodo,
>
> mit den Kongruenzen tust Du Dich aber immer noch schwer...
>
> > Aber wie sieht es denn mit 4X [mm]\equiv[/mm] 1 mod 5 aus?
> > ggt(5,4)=1
> >
> > -> X [mm]\equiv[/mm] 1 mod 5 (wenn ja Rest 1 dort steht, dann ist
> > dies ja auch für "aX" gegeben, richtig? Bzw. der Rest des
> > eukl. Algor. stimmt mit dem ggT überein...
>
> Das ist wahrscheinlich nur kraus formuliert, aber ich
> verstehe es jedenfalls nicht. Da [mm]4\equiv -1\mod{5}[/mm] ist,
> "sieht" man die Lösung [mm]X\equiv -1\equiv 4\mod{5}[/mm] aber auch
> ohne erw.euklid.Algo....
>
> > Nun aber zu 8X [mm]\equiv[/mm] 5 mod 11
> > ggT(11,8)=1 aber mit was kann ich denn hier kürzen?
>
> Hier ist nichts zu kürzen. Entweder Du kommst darauf, dass
> auch [mm]16\equiv 5\mod{11}[/mm] ist - und dann kannst Du kürzen,
> oder Du gehst eben den Algorithmus durch; besonders lang
> ist er ja hier nicht.
Entweder hast du dich jetzt vertan oder ich check es wirklich nicht.
Mit was will ich denn [mm] 16\equiv 5\mod{11} [/mm] kürzen? Da fällt mir nicht so wirklich viel zu ein...
> Hatte zur ganzen Aufgabe eigentlich schon jemand den
> Begriff "Chinesischer Rest(e)satz" in die Runde geworfen?
Um diesen geht es ja gerade auch...Nach welchem Schema ich das dann mache ist ja klar. Nur ich versteh einfach die "Umwandlung" der Kongruenzen nicht. Wenn 1X [mm] \equiv [/mm] c mod m dort steht ist es ja leicht. Aber sobald [mm] 2X\equiv [/mm] c mod m dort steht hakt es und ich weiß nicht wie ich das gescheit auf eine Darstellung mit X bekomme. Mit dem erw. euklid. Algor. sagt mir ja auch was. Aber wie es dann zu der geforderten Darstellung [mm] X\equiv [/mm] c mod m kommt, weiß ich leider Gottes immer noch nicht...
>
> Grüße
> reverend
Grüße
|
|
|
| |
|
Hallo nochmal,
wieso passieren Stromausfälle immer dann, wenn ich gerade meinen Artikel fertig geschrieben, aber noch nicht abgesandt habe? ![[motz]](/images/smileys/motz.gif "[motz]")
...
> > > Nun aber zu 8X [mm]\equiv[/mm] 5 mod 11
> > > ggT(11,8)=1 aber mit was kann ich denn hier
> kürzen?
> >
> > Hier ist nichts zu kürzen. Entweder Du kommst darauf, dass
> > auch [mm]16\equiv 5\mod{11}[/mm] ist - und dann kannst Du kürzen,
> > oder Du gehst eben den Algorithmus durch; besonders lang
> > ist er ja hier nicht.
>
> Entweder hast du dich jetzt vertan oder ich check es
> wirklich nicht.
> Mit was will ich denn [mm]16\equiv 5\mod{11}[/mm] kürzen? Da
> fällt mir nicht so wirklich viel zu ein...
Seufz. Das kannst Du auch nicht kürzen. Aber wenn Du a=b gegeben hast und Dir jemand verrät, das b=c ist, dann solltest Du sicher auch mal nachsehen, ob nicht a=c der eigentliche Tipp ist.
Und dann kannst Du kürzen: [mm] 8X\equiv 16\mod{11}
[/mm]
> > Hatte zur ganzen Aufgabe eigentlich schon jemand den
> > Begriff "Chinesischer Rest(e)satz" in die Runde geworfen?
>
> Um diesen geht es ja gerade auch...Nach welchem Schema ich
> das dann mache ist ja klar. Nur ich versteh einfach die
> "Umwandlung" der Kongruenzen nicht. Wenn 1X [mm]\equiv[/mm] c mod m
> dort steht ist es ja leicht. Aber sobald [mm]2X\equiv[/mm] c mod m
> dort steht hakt es und ich weiß nicht wie ich das gescheit
> auf eine Darstellung mit X bekomme. Mit dem erw. euklid.
> Algor. sagt mir ja auch was. Aber wie es dann zu der
> geforderten Darstellung [mm]X\equiv[/mm] c mod m kommt, weiß ich
> leider Gottes immer noch nicht...
Tja. Dann mach Dir doch mal eine Restklassenmultiplikationstabelle für den Modul 5. Und gleich noch eine für den Modul 11, auch wenn das mehr als viermal soviel zu schreiben ist (ja, danke, ich kann kopfrechnen).
"Viermal" geht davon aus, dass Du die Nullspalte und -zeile weglässt. Sie trägt ja für die Inversion der Multiplikation auch nichts aus.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:41 Sa 15.01.2011 | | Autor: | Bodo0686 |
Also mal ein anderes Beispiel:
Ich will 3 in [mm] \IZ [/mm] \ 20 [mm] \IZ [/mm] berechnen.
Also muss ich doch folgende Gleichung lösen:
[mm] 3X\equiv [/mm] 1 mod 20
oder 3X-1 = 20y
20=6*3+2
3=1*2+1
Rückwärts: 1=3-1*2 = 3-1*20+1*18 = 3+1*18 -1*20 = 3*7 - 1*20
Also ist 7 das Inverse zu 3 richtig?
Jetzt auf unseren Fall
[mm] 8X\equiv [/mm] 5 mod 11
Löse nun: 8X-5=11y
11=1*8+3
8=2*3+2
3=1*2+1
Rückwärts: 1= 3-1*2 = 3-1*(8-2*3)=3-1*(8-2*(11-1*8))=3-1*(8-2*11+2*8)=3-1(8-22+16)=3-1*8+1*22-1*16=3-8+22-16
aber wie kann ich jetzt hier das inverse ablesen?
Das stimmt doch schon wieder nicht...
Denn beim chinesischen Restsatz brauche ich ja ein Inverses!
Grüße
|
|
|
| |
|
Hallo,
> Also mal ein anderes Beispiel:
>
> Ich will 3 in [mm]\IZ[/mm] \ 20 [mm]\IZ[/mm] berechnen.
> Also muss ich doch folgende Gleichung lösen:
>
> [mm]3X\equiv[/mm] 1 mod 20
> oder 3X-1 = 20y
>
> 20=6*3+2
> 3=1*2+1
>
> Rückwärts: 1=3-1*2 = 3-1*20+1*18 = 3+1*18 -1*20 = 3*7 -
> 1*20
> Also ist 7 das Inverse zu 3 richtig?
Ja, das stimmt.
> Jetzt auf unseren Fall
>
> [mm]8X\equiv[/mm] 5 mod 11
> Löse nun: 8X-5=11y
>
> 11=1*8+3
> 8=2*3+2
> 3=1*2+1
>
> Rückwärts: 1= 3-1*2 =
> 3-1*(8-2*3)=3-1*(8-2*(11-1*8))=3-1*(8-2*11+2*8)=3-1(8-22+16)=3-1*8+1*22-1*16=3-8+22-16
> aber wie kann ich jetzt hier das inverse ablesen?
So kannst du es nicht ablesen. Da fehlen wesentliche Schritte der Rückrechnung. So gehts:
1=3-1*2=3-1*(8-2*3)=...
[jetzt hast Du alles durch Vielfache von 8 und 3 dargestellt, aber hier sollte man erstmal zusammenfassen, also:]
...=3+2*3-1*8=3*3-1*8=...
[jetzt die 3 ersetzen, und dann die 8er und die 11er jeweils zusammenfassen]
...=3*(11-8)-8=3*11-4*8
Also ist -4 das Inverse zu 8 [mm] \mod{11} [/mm] (also 7), aber 7 ist noch nicht die Lösung der gegebenen Kongruenz.
> Das stimmt doch schon wieder nicht...
Genau, das stimmte nicht. Aber war irgendwas an meinem viel kürzeren Lösungsweg [mm] 8X\equiv 16\mod{11} [/mm] unverständlich?
> Denn beim chinesischen Restsatz brauche ich ja ein
> Inverses!
Ja. Aber Du brauchst hier nicht das Inverse zur 8, sondern erstmal die Vereinfachung Deiner Kongruenz auf [mm] X\equiv\cdots\mod{11}.
[/mm]
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:52 Sa 15.01.2011 | | Autor: | Bodo0686 |
Also,
haben wir jetzt:
[mm] X\equiv [/mm] 1 mod 4
[mm] X\equiv [/mm] 1 mod 5
[mm] X\equiv [/mm] 2 mod 11
Bestimme kgV=220=4*5*11
i 1 2 3
[mm] c_i [/mm] 1 1 2
[mm] m_i [/mm] 4 5 11
[mm] n_i [/mm] 55 44 20
[mm] n_i^{-1} [/mm] mod [mm] m_i [/mm] 3 4 9
[mm] n_1=55 \equiv [/mm] 3 mod 4
[mm] n_2=44 \equiv [/mm] 4 mod 5
[mm] n_3=20 \equiv [/mm] 9 mod 11
[mm] X=\summe_{i=1}^{3} c_i*n_i*n_i^{-1}=1*55*3+1*44*4+2*20*9\equiv [/mm] 41 mod 220
|
|
|
| |
|
Hallo,
mach mal die Probe. Ist denn [mm] 41\equiv 2\mod{11} [/mm] ?
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:05 Sa 15.01.2011 | | Autor: | Bodo0686 |
> Hallo,
>
> mach mal die Probe. Ist denn [mm]41\equiv 2\mod{11}[/mm] ?
>
> lg
> rev
>
Hallo,
nein. Es ist 41 [mm] \equiv [/mm] 8 mod 11
Aber wo steckt mein Fehler?
Grüße
|
|
|
| |
|
Hallo Bodo,
am besten rechnest Du sowieso das ganze nochmal, weil auch ein Fehler in Deinen Voraussetzungen steckt. Folgendes System ist zu lösen:
[mm] X\equiv 1\mod{4}
[/mm]
[mm] X\equiv \blue{4} \mod{5}
[/mm]
[mm] X\equiv 2\mod{11}
[/mm]
Herauskommen sollte dann [mm] X\equiv 189\mod{220}.
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:16 Sa 15.01.2011 | | Autor: | Bodo0686 |
Hallo,
ich komme nicht auf dein Ergebnis:
ich habe: kgv=220
i 1 2 3
[mm] c_i [/mm] 1 4 2
[mm] m_i [/mm] 4 5 11
[mm] n_i [/mm] 55 44 20
[mm] n_i^{-1} [/mm] 3 4 9
X=1*55*3+4*4*44+2*20*9=1229
1229 mod 220 = 129
Grüße
|
|
|
| |
|
Hallo,
> Hallo,
>
> ich komme nicht auf dein Ergebnis:
>
> ich habe: kgv=220
>
> i 1 2 3
> [mm]c_i[/mm] 1 4 2
> [mm]m_i[/mm] 4 5 11
> [mm]n_i[/mm] 55 44 20
Bis hierhin stimmts.
> [mm]n_i^{-1}[/mm] 3 4 9
Und wie hast Du die ermittelt?
Ich komme da auf -1, -1, -6
und damit auf X=1*55*(-1)+4*44*(-1)+2*20*(-6)=-(55+176+240)=-471
$ [mm] -471\mod{220}\equiv [/mm] 189 $
> X=1*55*3+4*4*44+2*20*9=1229
> 1229 mod 220 = 129
Hier stimmt wieder die Probe mod 11 nicht.
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:43 Sa 15.01.2011 | | Autor: | Bodo0686 |
Hallo,
also ich habe:
[mm] n_1=55\equiv [/mm] 3 mod 4
[mm] n_2=44\equiv [/mm] 4 mod 5
[mm] n_3=20\equiv [/mm] 9 mod 11
Grüße
|
|
|
| |
|
Hallo,
> also ich habe:
>
> [mm]n_1=55\equiv[/mm] 3 mod 4
> [mm]n_2=44\equiv[/mm] 4 mod 5
> [mm]n_3=20\equiv[/mm] 9 mod 11
Nein, zu lösen ist dies:
[mm] 55n_1\equiv 1\mod{4}
[/mm]
[mm] 44n_2\equiv 1\mod{5}
[/mm]
[mm] 20n_3\equiv 1\mod{11}
[/mm]
Mit positiven Lösungen/Restklassen ist das äquivalent zu:
[mm] n_1\equiv 3\mod{4} [/mm] (zufällig das gleiche wie bei Dir)
[mm] n_2\equiv 4\mod{5} [/mm] (ebenso zufällig das gleiche)
[mm] n_3\equiv 5\mod{11} [/mm] (und deswegen stimmt die 11er-Probe auch nicht)
Ich betone, dass die ersten beiden Kongruenzen hier nur zufällig gleich sind. Dein Ansatz stimmt nicht.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:53 Sa 15.01.2011 | | Autor: | Bodo0686 |
ok, damit wären wir wieder am Anfang :-/
[mm] 55n_1\equiv 1\mod{4} [/mm]
Also löse ich jetzt: [mm] 55n_1-1=4y
[/mm]
4y mittels erw. eukl. Algor. bestimmen?
Oder wie bestimmt man das jetzt? Ich brauche ja das Inverse...
Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:41 Sa 15.01.2011 | | Autor: | Bodo0686 |
Wir hatten ein Bsp in der Vorlesung
[mm] X\equiv [/mm] 2 mod 3
[mm] X\equiv [/mm] 3 mod 5
[mm] X\equiv [/mm] 2 mod 7
KGV=105
i 1 2 3
[mm] c_i [/mm] 2 3 2
[mm] m_i [/mm] 3 5 7
[mm] n_i [/mm] 35 21 15
[mm] n_i^{-1} [/mm] 2 1 1 (obwohl bei 2 (-1) steht)
[mm] n_1=35 \equiv [/mm] 2 mod 3
[mm] n_2=21 \equiv [/mm] 1 mod 5
[mm] n_3=15 \equiv [/mm] 1 mod 7
X=23
Hier haben wir doch auch bei der Bestimmung der Inversen 35 mod 3 gerechnet, dort kam 2 raus. Nur oben war dies kongurent zu (-1), wieso keine Ahnung.
Rest wurde analog so gelöst...
Ich verstehs nicht...
Grüße
|
|
|
| |
|
Hallo nochmal,
das ist sowohl in dem Vorlesungsbeispiel als auch in der aktuellen Aufgabe genau dann das gleiche Ergebnis, wenn [mm] X^2\equiv{1} [/mm] ist.
So gilt eben sowohl [mm] 35\equiv 2\mod{3} [/mm] als auch [mm] 35*2\equiv 1\mod{3}.
[/mm]
Außerdem gilt auch noch [mm] -2\equiv 1\mod{3}, [/mm] und damit sollten alle Verwirrungen, Verwicklungen und Verwechslungen jetzt aufgeklärt sein.
lg
rev
|
|
|
| |
|
Jaaa.... Hallo.
> ok, damit wären wir wieder am Anfang :-/
>
> [mm]55n_1\equiv 1\mod{4}[/mm]
>
> Also löse ich jetzt: [mm]55n_1-1=4y[/mm]
> 4y mittels erw. eukl. Algor. bestimmen?
Eigentlich interessiert Dich doch nur [mm] n_1. [/mm] Und [mm] \mod{4} [/mm] geht das nun wirklich im Kopf und ohne das große Gedöns. [mm] \mod{2011} [/mm] hätte man vielleicht mehr Aufwand zu treiben.
Also erstmal kann man ja vereinfachen: [mm] 55n_1\equiv 3n_1\equiv 1\mod{4}
[/mm]
Oder, wenns Dir lieber ist, geht auch [mm] (-1)*n_1 \equiv 1\mod{4}.
[/mm]
> Oder wie bestimmt man das jetzt? Ich brauche ja das
> Inverse...
Naja, bei so kleinen Moduln kann man sich auch bequem mal durchprobieren. Es werden hier ja max. vier Versuche.
Genau eine der folgenden Gleichungen muss lösbar sein:
[mm] 3n_1=1+0*4
[/mm]
[mm] 3n_1=1+1*4
[/mm]
[mm] 3n_1=1+2*4
[/mm]
[mm] 3n_1=1+3*4
[/mm]
Also geht man im Kopf mal durch, ob bei 1,5,9,13 eine durch drei teilbare Zahl dabei. Die teilen, und man hat das Ergebnis.
lg
rev
> Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:32 Sa 15.01.2011 | | Autor: | Bodo0686 |
Also kann ich den letzten Fall auch so schreiben?
[mm] 20n_3 \equiv 5n_3 \equiv [/mm] 1 mod 11
[mm] 5n_3=1+0*11 [/mm] usw.
Grüße
|
|
|
| |
|
Hallo nochmal,
> Also kann ich den letzten Fall auch so schreiben?
>
> [mm]20n_3 \equiv 5n_3 \equiv[/mm] 1 mod 11
Seit wann gilt [mm] 20\equiv 5\mod{11} [/mm] ? Oder rechnest Du gerade mit 6-adischen Zahlen?
> [mm]5n_3=1+0*11[/mm] usw.
Die Methode klappt natürlich auch hier: [mm] \blue{9}n_3=1+0*11 [/mm] usw.
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:50 Sa 15.01.2011 | | Autor: | Bodo0686 |
also ist das die 9 die ich vorher ausgerechnet habe?
Wenn dem so ist, dann blicke ich wohl langsam dadurch...
grüße
|
|
|
| |
|
Hallo nochmal.
Naja. [mm] 20\equiv 9\mod{11} [/mm] ist ja noch Rechnen auf Grundschulniveau, nur in neuer Verkleidung.
Interessant ist doch erst die Auflösung von [mm] 9n_3\equiv 1\mod{11} [/mm] zu [mm] n_3\equiv{5}\mod{11}. [/mm] Auch das kann man Grundschülern noch erklären, sie können das kleine 1*1 (hier: 5*9) und wissen noch am besten, was ein Rest bei einer Division ist, hier durch 11.
Lass Dich also nicht von der neuen Hülle der Modulrechnung abschrecken. Eigentlich ist es alles ganz einfach. Schön, die Algorithmen sind etwas länger, aber die Grundidee ist noch die gleiche wie bei den Grundrechenarten.
lg
rev
|
|
|
|
