Kongruenzsysteme lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Löse das System
5x [mm] \equiv [/mm] 2 mod 3
8x [mm] \equiv [/mm] 5 mod 9
2x [mm] \equiv [/mm] 6 mod 10 |
Hallöchen,
ich habe ein Problem beim lösen der obigen Aufgabe. Ich verstehe ich nicht wie ich die gegebenen Kongruenzen umformen kann, d.h.
wie ich aus 5x [mm] \equiv [/mm] 2 mod 3 eine Kongruenz der Art x [mm] \equiv [/mm] ... bekomme.
Kann mir das bitte jemand erklären? ich komme da einfach auf keinen grünen Zweig.
LG Schmetterfee
|
|
| |
|
Hallo Schmetterfee,
> Löse das System
> 5x [mm]\equiv[/mm] 2 mod 3
> 8x [mm]\equiv[/mm] 5 mod 9
> 2x [mm]\equiv[/mm] 6 mod 10
> Hallöchen,
>
> ich habe ein Problem beim lösen der obigen Aufgabe. Ich
> verstehe ich nicht wie ich die gegebenen Kongruenzen
> umformen kann, d.h.
>
> wie ich aus 5x [mm]\equiv[/mm] 2 mod 3 eine Kongruenz der Art x
> [mm]\equiv[/mm] ... bekomme.
5 ist kongruent 2 modulo 3. Dann steht da:
[mm]2x \equiv 2 \operatorname{mod} \ 3[/mm]
Jetzt berechne das multiplikative Inverse von 2 in dieser Restklasse.
> Kann mir das bitte jemand erklären? ich komme da einfach
> auf keinen grünen Zweig.
>
> LG Schmetterfee
Gruss
MathePower
|
|
|
| |
|
Hallöchen
>
> > Löse das System
> > 5x [mm]\equiv[/mm] 2 mod 3
> > 8x [mm]\equiv[/mm] 5 mod 9
> > 2x [mm]\equiv[/mm] 6 mod 10
> > Hallöchen,
> >
> > ich habe ein Problem beim lösen der obigen Aufgabe. Ich
> > verstehe ich nicht wie ich die gegebenen Kongruenzen
> > umformen kann, d.h.
> >
> > wie ich aus 5x [mm]\equiv[/mm] 2 mod 3 eine Kongruenz der Art x
> > [mm]\equiv[/mm] ... bekomme.
>
>
> 5 ist kongruent 2 modulo 3. Dann steht da:
>
> [mm]2x \equiv 2 \operatorname{mod} \ 3[/mm]
>
> Jetzt berechne das multiplikative Inverse von 2 in dieser
> Restklasse.
>
Naja das ist ja 2, denn (2 mod 3) * (2 mod 3)= 4 mod 3= 1 mod 3
also erhalte ich x [mm] \equiv [/mm] 1 mod 3
und für 8x [mm]\equiv[/mm] 5 mod 9 erhalte ich x [mm] \equiv [/mm] 4 mod 9
und 2x [mm]\equiv[/mm] 6 mod 10 ist x [mm] \equiv [/mm] 3 mod 5
ist das so richtig oder habe ich mich irgendwo verrechnet?
LG Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> > > Löse das System
> > > 5x [mm]\equiv[/mm] 2 mod 3
> > > 8x [mm]\equiv[/mm] 5 mod 9
> > > 2x [mm]\equiv[/mm] 6 mod 10
> >
> > 5 ist kongruent 2 modulo 3. Dann steht da:
> >
> > [mm]2x \equiv 2 \operatorname{mod} \ 3[/mm]
> >
> > Jetzt berechne das multiplikative Inverse von 2 in dieser
> > Restklasse.
> >
> Naja das ist ja 2, denn (2 mod 3) * (2 mod 3)= 4 mod 3= 1
> mod 3
Wenn Du im Verlauf dieser Äquivalenzkette nur einmal "mod 3" schreibst, ist das genug. Ansonsten richtig!
> also erhalte ich x [mm]\equiv[/mm] 1 mod 3
> und für 8x [mm]\equiv[/mm] 5 mod 9 erhalte ich x [mm]\equiv[/mm] 4 mod 9
> und 2x [mm]\equiv[/mm] 6 mod 10 ist x [mm]\equiv[/mm] 3 mod 5
Ja, alles korrekt. ![[ok]](/images/smileys/ok.gif "[ok]")
Eine der drei Kongruenzen kannst Du jetzt noch unter den Tisch fallen lassen. Dann chinesischer Restsatz.
Kontrollergebnis: [mm] x\equiv 13\mod{45}
[/mm]
Grüße
reverend
|
|
|
| |
|
Hallöchen
>
> > > > Löse das System
> > > > 5x [mm]\equiv[/mm] 2 mod 3
> > > > 8x [mm]\equiv[/mm] 5 mod 9
> > > > 2x [mm]\equiv[/mm] 6 mod 10
> > >
> > > 5 ist kongruent 2 modulo 3. Dann steht da:
> > >
> > > [mm]2x \equiv 2 \operatorname{mod} \ 3[/mm]
> > >
> > > Jetzt berechne das multiplikative Inverse von 2 in dieser
> > > Restklasse.
> > >
> > Naja das ist ja 2, denn (2 mod 3) * (2 mod 3)= 4 mod 3= 1
> > mod 3
>
> Wenn Du im Verlauf dieser Äquivalenzkette nur einmal "mod
> 3" schreibst, ist das genug. Ansonsten richtig!
>
> > also erhalte ich x [mm]\equiv[/mm] 1 mod 3
> > und für 8x [mm]\equiv[/mm] 5 mod 9 erhalte ich x [mm]\equiv[/mm] 4 mod
> 9
> > und 2x [mm]\equiv[/mm] 6 mod 10 ist x [mm]\equiv[/mm] 3 mod 5
>
> Ja, alles korrekt.
>
> Eine der drei Kongruenzen kannst Du jetzt noch unter den
> Tisch fallen lassen. Dann chinesischer Restsatz.
>
Wieso kann ich eine der Kongruenzen unter den Tisch fallen lassen?
> Kontrollergebnis: [mm]x\equiv 13\mod{45}[/mm]
>
Habe ich auch raus gefunden^^
LG Schmetterfee
|
|
|
| |
|
Hallöchen,
ich habe meinen Rechenfahler schon gefunden. aber danke für die Mühe.
Lg Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> Hallöchen
> >
> > > > > Löse das System
> > > > > 5x [mm]\equiv[/mm] 2 mod 3
> > > > > 8x [mm]\equiv[/mm] 5 mod 9
> > > > > 2x [mm]\equiv[/mm] 6 mod 10
> > > >
> > > > 5 ist kongruent 2 modulo 3. Dann steht da:
> > > >
> > > > [mm]2x \equiv 2 \operatorname{mod} \ 3[/mm]
> > > >
> > > > Jetzt berechne das multiplikative Inverse von 2 in dieser
> > > > Restklasse.
> > > >
> > > Naja das ist ja 2, denn (2 mod 3) * (2 mod 3)= 4 mod 3= 1
> > > mod 3
> >
> > Wenn Du im Verlauf dieser Äquivalenzkette nur einmal "mod
> > 3" schreibst, ist das genug. Ansonsten richtig!
> >
> > > also erhalte ich x [mm]\equiv[/mm] 1 mod 3
> > > und für 8x [mm]\equiv[/mm] 5 mod 9 erhalte ich x [mm]\equiv[/mm] 4
> mod
> > 9
> > > und 2x [mm]\equiv[/mm] 6 mod 10 ist x [mm]\equiv[/mm] 3 mod 5
> >
> > Ja, alles korrekt.
> >
> > Eine der drei Kongruenzen kannst Du jetzt noch unter den
> > Tisch fallen lassen. Dann chinesischer Restsatz.
> >
> Wieso kann ich eine der Kongruenzen unter den Tisch fallen
> lassen?
>
Nun, weil [mm]x \equiv 4 \operatorname{mod} 9[/mm] gleichbedeutend mit [mm]x \equiv 1 \operatorname{mod} 3[/mm] ist.
> > Kontrollergebnis: [mm]x\equiv 13\mod{45}[/mm]
> >
> Habe ich auch raus gefunden^^
>
> LG Schmetterfee
Gruss
MathePower
|
|
|
| |
|
| Aufgabe | Löse das System
3x+7y [mm] \equiv [/mm] 10 mod 14
11x -8y [mm] \equiv [/mm] 6 mod 14 |
Hallöchen,
mit einer Variable habe ich ja nun schon verstanden wie ich solche systeme löse. aber wie gehe ich dann an so eine Aufgabe ran? kann ich das auch irgendwie umschreiben zu x [mm] \equiv [/mm] ...?
Wäre für einen Tipp sehr dankbar.
LG schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:23 So 20.11.2011 | | Autor: | leduart |
Hallo
du kannst wie in einem gewöhnlichen System rechnen, wenn du über 14 rauskommst mod 14 verkleinern
und nie dividieren, sondern immer mit dem mult. Inversen, (falls es existiert) mult.
Gruss leduart
|
|
|
| |
|
Hallöchen,
aber wie soll ich denn damit normal rechnen? ich habe ja keine Variable die sich wegkürzen lässt?
LG Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> aber wie soll ich denn damit normal rechnen? ich habe ja
> keine Variable die sich wegkürzen lässt?
Die hast Du doch in einem anderen linearen Gleichungssystem auch nicht. Was meinst Du damit?
[mm] 3x+7y\equiv 10\mod{14}
[/mm]
11x-8y [mm] \equiv 6\mod{14}
[/mm]
Wie sonst auch: z.B. 11mal die erste Gleichung minus 3mal die zweite - das führt auf
[mm] 0x+101y\equiv 92\mod{14}
[/mm]
Die 0x fallen weg; ansonsten leduarts Tipp berücksichtigen, also auch die Koeffizienten [mm] \mod{14} [/mm] "behandeln" - das führt auf
[mm] 3y\equiv 8\mod{14}
[/mm]
Nun gibt es ja ein zu 3 multiplikativ Inverses, so dass diese Äquivalenz also auflösbar ist. Dann in eine der ursprünglichen beiden Gleichungen einsetzen und entsprechend nach x auflösen.
Grüße
reverend
|
|
|
| |
|
Hallöchen,
>
> > aber wie soll ich denn damit normal rechnen? ich habe ja
> > keine Variable die sich wegkürzen lässt?
>
> Die hast Du doch in einem anderen linearen Gleichungssystem
> auch nicht. Was meinst Du damit?
>
ja war ein bisschen doof ausgedrückt aber ich wusste nicht wie ich mit 2 variablen im Kongruenzsystem umgehen soll.
> [mm]3x+7y\equiv 10\mod{14}[/mm]
> 11x-8y [mm]\equiv 6\mod{14}[/mm]
>
> Wie sonst auch: z.B. 11mal die erste Gleichung minus 3mal
> die zweite - das führt auf
>
> [mm]0x+101y\equiv 92\mod{14}[/mm]
>
> Die 0x fallen weg; ansonsten leduarts Tipp
> berücksichtigen, also auch die Koeffizienten [mm]\mod{14}[/mm]
> "behandeln" - das führt auf
> [mm]3y\equiv 8\mod{14}[/mm]
>
> Nun gibt es ja ein zu 3 multiplikativ Inverses, so dass
> diese Äquivalenz also auflösbar ist. Dann in eine der
> ursprünglichen beiden Gleichungen einsetzen und
> entsprechend nach x auflösen.
>
Ich erhalte y [mm] \equiv [/mm] 12 mod 14
wenn ich das einsetze erhalte ich ja:
3x+ 7* (12 mod 14) [mm] \equiv [/mm] 10 mod 14
3x+(84 mod 14) [mm] \equiv [/mm] 10 mod 14
3x+ 0 mod 14 [mm] \equiv [/mm] 10 mod 14
dies kommt mir aber irgendwie spanisch vor. bin noch etwas unsicher im rechnen mit Kongruenzen mache ich das soweit richtig?
Lg Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> Hallöchen,
> >
> > > aber wie soll ich denn damit normal rechnen? ich habe ja
> > > keine Variable die sich wegkürzen lässt?
> >
> > Die hast Du doch in einem anderen linearen Gleichungssystem
> > auch nicht. Was meinst Du damit?
> >
> ja war ein bisschen doof ausgedrückt aber ich wusste nicht
> wie ich mit 2 variablen im Kongruenzsystem umgehen soll.
>
> > [mm]3x+7y\equiv 10\mod{14}[/mm]
> > 11x-8y [mm]\equiv 6\mod{14}[/mm]
> >
> > Wie sonst auch: z.B. 11mal die erste Gleichung minus 3mal
> > die zweite - das führt auf
> >
> > [mm]0x+101y\equiv 92\mod{14}[/mm]
> >
> > Die 0x fallen weg; ansonsten leduarts Tipp
> > berücksichtigen, also auch die Koeffizienten [mm]\mod{14}[/mm]
> > "behandeln" - das führt auf
> > [mm]3y\equiv 8\mod{14}[/mm]
> >
> > Nun gibt es ja ein zu 3 multiplikativ Inverses, so dass
> > diese Äquivalenz also auflösbar ist. Dann in eine der
> > ursprünglichen beiden Gleichungen einsetzen und
> > entsprechend nach x auflösen.
> >
> Ich erhalte y [mm]\equiv[/mm] 12 mod 14
> wenn ich das einsetze erhalte ich ja:
> 3x+ 7* (12 mod 14) [mm]\equiv[/mm] 10 mod 14
> 3x+(84 mod 14) [mm]\equiv[/mm] 10 mod 14
> 3x+ 0 mod 14 [mm]\equiv[/mm] 10 mod 14
>
> dies kommt mir aber irgendwie spanisch vor. bin noch etwas
> unsicher im rechnen mit Kongruenzen mache ich das soweit
> richtig?
>
Ja, das ist soweit richtig.
> Lg Schmetterfee
Gruss
MathePower
|
|
|
| |
|
Hallöchen
>
> > Hallöchen,
> > >
> > > > aber wie soll ich denn damit normal rechnen? ich habe ja
> > > > keine Variable die sich wegkürzen lässt?
> > >
> > > Die hast Du doch in einem anderen linearen Gleichungssystem
> > > auch nicht. Was meinst Du damit?
> > >
> > ja war ein bisschen doof ausgedrückt aber ich wusste nicht
> > wie ich mit 2 variablen im Kongruenzsystem umgehen soll.
> >
> > > [mm]3x+7y\equiv 10\mod{14}[/mm]
> > > 11x-8y [mm]\equiv 6\mod{14}[/mm]
>
> > >
> > > Wie sonst auch: z.B. 11mal die erste Gleichung minus 3mal
> > > die zweite - das führt auf
> > >
> > > [mm]0x+101y\equiv 92\mod{14}[/mm]
> > >
> > > Die 0x fallen weg; ansonsten leduarts Tipp
> > > berücksichtigen, also auch die Koeffizienten [mm]\mod{14}[/mm]
> > > "behandeln" - das führt auf
> > > [mm]3y\equiv 8\mod{14}[/mm]
> > >
> > > Nun gibt es ja ein zu 3 multiplikativ Inverses, so dass
> > > diese Äquivalenz also auflösbar ist. Dann in eine der
> > > ursprünglichen beiden Gleichungen einsetzen und
> > > entsprechend nach x auflösen.
> > >
> > Ich erhalte y [mm]\equiv[/mm] 12 mod 14
> > wenn ich das einsetze erhalte ich ja:
> > 3x+ 7* (12 mod 14) [mm]\equiv[/mm] 10 mod 14
> > 3x+(84 mod 14) [mm]\equiv[/mm] 10 mod 14
> > 3x+ 0 mod 14 [mm]\equiv[/mm] 10 mod 14
> >
> > dies kommt mir aber irgendwie spanisch vor. bin noch etwas
> > unsicher im rechnen mit Kongruenzen mache ich das soweit
> > richtig?
> >
>
>
> Ja, das ist soweit richtig.
>
>
Aber dann bekomme ich doch ein Problem. Denn wenn ich dann
3x [mm] \equiv [/mm] 10 mod 14 ausrechne erhalte ich
x [mm] \equiv [/mm] 8 mod 14
und das so berechnete x und y löst aber nicht die zweite Gleichung meines Systems also wo liegt der Fehler?
LG Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> Hallöchen
> >
> > > Hallöchen,
> > > >
> > > > > aber wie soll ich denn damit normal rechnen? ich habe ja
> > > > > keine Variable die sich wegkürzen lässt?
> > > >
> > > > Die hast Du doch in einem anderen linearen Gleichungssystem
> > > > auch nicht. Was meinst Du damit?
> > > >
> > > ja war ein bisschen doof ausgedrückt aber ich wusste nicht
> > > wie ich mit 2 variablen im Kongruenzsystem umgehen soll.
> > >
> > > > [mm]3x+7y\equiv 10\mod{14}[/mm]
> > > > 11x-8y [mm]\equiv 6\mod{14}[/mm]
>
> >
> > > >
> > > > Wie sonst auch: z.B. 11mal die erste Gleichung minus 3mal
> > > > die zweite - das führt auf
> > > >
> > > > [mm]0x+101y\equiv 92\mod{14}[/mm]
> > > >
> > > > Die 0x fallen weg; ansonsten leduarts Tipp
> > > > berücksichtigen, also auch die Koeffizienten [mm]\mod{14}[/mm]
> > > > "behandeln" - das führt auf
> > > > [mm]3y\equiv 8\mod{14}[/mm]
> > > >
> > > > Nun gibt es ja ein zu 3 multiplikativ Inverses, so dass
> > > > diese Äquivalenz also auflösbar ist. Dann in eine der
> > > > ursprünglichen beiden Gleichungen einsetzen und
> > > > entsprechend nach x auflösen.
> > > >
> > > Ich erhalte y [mm]\equiv[/mm] 12 mod 14
> > > wenn ich das einsetze erhalte ich ja:
> > > 3x+ 7* (12 mod 14) [mm]\equiv[/mm] 10 mod 14
> > > 3x+(84 mod 14) [mm]\equiv[/mm] 10 mod 14
> > > 3x+ 0 mod 14 [mm]\equiv[/mm] 10 mod 14
> > >
> > > dies kommt mir aber irgendwie spanisch vor. bin noch etwas
> > > unsicher im rechnen mit Kongruenzen mache ich das soweit
> > > richtig?
> > >
> >
> >
> > Ja, das ist soweit richtig.
> >
> >
> Aber dann bekomme ich doch ein Problem. Denn wenn ich dann
> 3x [mm]\equiv[/mm] 10 mod 14 ausrechne erhalte ich
> x [mm]\equiv[/mm] 8 mod 14
>
> und das so berechnete x und y löst aber nicht die zweite
> Gleichung meines Systems also wo liegt der Fehler?
>
Die 2. Gleichung wird auch gelöst:
[mm]11x-8y = 11*8-8*12 =88-96=-8 \equiv -8+14=6 \operatorname{mod} \ 14[/mm]
> LG Schmetterfee
Gruss
MathePower
|
|
|
| |
|
Hallöchen
>
> [mm]11x-8y = 11*8-8*12 =88-96=-8 \equiv -8+14=6 \operatorname{mod} \ 14[/mm]
>
>
stimmt ich war bei mir in meinen Aufzeichnungen verrutscht. Ne doofe Frage weil es ja nun ne Gleichung ersten Grades ist aber auch in Kongruenzsystemen gibt es doch nicht mehr als eine Lösung oder?
Wie würde ich denn hier die Lösungsmenge angeben?für x und y getrennt voneinader also als x Lösungsmenge= {8+K*14} und für y={12+K*14} oder gibt es auch ne Möglichkeit die zusammengefast zuformulieren?
LG Schmetterfee
|
|
|
| |
|
Hallo Schmetterfee,
> Hallöchen
>
> >
> > [mm]11x-8y = 11*8-8*12 =88-96=-8 \equiv -8+14=6 \operatorname{mod} \ 14[/mm]
>
> >
> >
> stimmt ich war bei mir in meinen Aufzeichnungen verrutscht.
> Ne doofe Frage weil es ja nun ne Gleichung ersten Grades
> ist aber auch in Kongruenzsystemen gibt es doch nicht mehr
> als eine Lösung oder?
>
In der Menge aller Restklassen gibt es
hier natürlich auch nur eine Lösung.
Es gibt aber unendlich viele ganze Zahlen,
die zu diesen Lösungen gehören.
> Wie würde ich denn hier die Lösungsmenge angeben?für x
> und y getrennt voneinader also als x Lösungsmenge=
> {8+K*14} und für y={12+K*14} oder gibt es auch ne
> Möglichkeit die zusammengefast zuformulieren?
>
Zum Beispiel so:
[mm]L=\left\{ \ x,y \in \IZ \left|\right x \equiv 8 \operatorname{mod} \ 14 \wedge y \equiv 12 \operatorname{mod} \ 14 \right\}[/mm]
> LG Schmetterfee
Gruss
MathePower
|
|
|
| |
|
Hallöchen,
danke für die schnelle Antwort. Jetzt ist mir die Thematik Kongruenzen noch klarer geworden. Vielen lieben Dank.
LG Schmetterfee
|
|
|
|
