lösungen der Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:22 Fr 03.06.2011 | | Autor: | anetteS |
| Aufgabe | Finde für b [mm] \in \IN [/mm] Lösungen x [mm] \in \IN [/mm] der folgenden Kongruenz:
5x [mm] \equiv [/mm] b (mod 6). |
Hallolchen!
Ich brauche bei der obigen Aufgabe Eure Hilfe.
Ich habe den folgenden Ansatz:
5x [mm] \equiv [/mm] b (mod 6) -> x [mm] \equiv [/mm] b/5 (mod 6)
b/5 muss aus N sein, also betrachte ich für b alle Vielfachen von 5.
Jetzt wollte ich einfach alle Möglichkeiten durchgehen:
z.B. für x [mm] \equiv [/mm] 5/5 (mod 6)= 1 (mod 6) folgt x=7+k*6 k=0,1,2...
für x [mm] \equiv [/mm] 10/5 (mod 6)= 2 (mod 6) folgt x=8+k*6
Das muss ich ja nur bis 30/5=b machen, denn da komme ich ja schon auf 0 (mod 6).
Ist dieser Lösungsweg soweit in Ordnung?
Gibt es eventuell einen anderen effektiveren, denn mein Lösungsweg würde bei größeren Zahlen sehr viel (Schreib)aufwand bedetuen.
Vielen Dank und viele Grüße,
Anette.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:47 Fr 03.06.2011 | | Autor: | Teufel |
Hi!
Es sieht ok aus, aber ja, das ist etwas zu umständlich.
Versuche stattdessen folgendes: Suche das Inverse von 5 modulo 6, also eine Zahl r, sodass [mm] $5r\equiv [/mm] 1$ mod 6 gilt. Denn dann kannst du beide Seiten *r rechnen und vor dem x steht nur noch eine 1.
In deinem Fall kannst du einfach mal alle Zahlen durchprobieren.
Wenn die Zahlen größer werden und du das nicht mehr so leicht überblicken kannst, benutze den erweiterten euklidischen Algorithmus, um ein Inverses zu finden.
In deinem Fall würde das so gehen:
ggT(5,6)=1, also existieren r, s, sodass 5r+6s=1 ist. Dabei ist das r, dasjenige r, das du brauchst. Finde also r, s, sodass die Gleichheit gilt und modulo 6 fällt dann 6s weg und dort steht [mm] $5r\equiv [/mm] 1$ mod 6.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:00 Sa 04.06.2011 | | Autor: | felixf |
Moin,
> Versuche stattdessen folgendes: Suche das Inverse von 5
> modulo 6, also eine Zahl r, sodass [mm]5r\equiv 1[/mm] mod 6 gilt.
> Denn dann kannst du beide Seiten *r rechnen und vor dem x
> steht nur noch eine 1.
>
> In deinem Fall kannst du einfach mal alle Zahlen
> durchprobieren.
wenn man bedenkt, dass $5 [mm] \equiv [/mm] -1 [mm] \pmod{6}$ [/mm] ist, geht es noch einfacher 
LG Felix
|
|
|
| |
|
Hi,
wie kann man die aufgabe mit dem tipp von felix lösen? habe nämlich ein ähnliches problem....
grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:35 Do 09.06.2011 | | Autor: | abakus |
> Hi,
>
> wie kann man die aufgabe mit dem tipp von felix lösen?
> habe nämlich ein ähnliches problem....
>
> grüße
Na,
wenn [mm] 5\equiv-1 [/mm] mod 6 gilt, dann gilt auch
[mm] 5x\equiv-1x [/mm] mod 6.
Somit muss auch [mm] -x\equiv [/mm] b mod 6 gelten.
Gruß Abakus
|
|
|
| |
|
Hi,
> Na,
> wenn $ [mm] 5\equiv-1 [/mm] $ mod 6 gilt, dann gilt auch
> $ [mm] 5x\equiv-1x [/mm] $ mod 6.
> Somit muss auch $ [mm] -x\equiv [/mm] $ b mod 6 gelten.
Wie kommtst du denn von $ [mm] 5x\equiv-1x [/mm] $ mod 6 auf $ [mm] -x\equiv [/mm] $ b mod 6??
Und was wäre dann mit $ [mm] -x\equiv [/mm] $ b mod 6 die Lösung des Problems [mm] 5x\equiv [/mm] b mod 6?? Irgendwie verstehe ich das noch nicht so ganz....
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:02 Do 09.06.2011 | | Autor: | abakus |
> Hi,
>
> > Na,
> > wenn [mm]5\equiv-1[/mm] mod 6 gilt, dann gilt auch
> > [mm]5x\equiv-1x[/mm] mod 6.
> > Somit muss auch [mm]-x\equiv[/mm] b mod 6 gelten.
>
> Wie kommtst du denn von [mm]5x\equiv-1x[/mm] mod 6 auf [mm]-x\equiv[/mm] b
> mod 6??
Deine Aufgabe lautete 5x [mm] \equiv [/mm] b mod 6.
Wegen -x [mm] \equiv [/mm] 5x mod 6 wird daraus
-x [mm] \equiv [/mm] 5x [mm] \equiv [/mm] b mod 6,
also -x [mm] \equiv [/mm] b mod 6.
>
> Und was wäre dann mit [mm]-x\equiv[/mm] b mod 6 die Lösung des
> Problems [mm]5x\equiv[/mm] b mod 6?? Irgendwie verstehe ich das noch
> nicht so ganz....
|
|
|
| |
|
entweder bin ich gerade bild, oder keine ahnung....
> Deine Aufgabe lautete 5x $ [mm] \equiv [/mm] $ b mod 6.
> Wegen -x $ [mm] \equiv [/mm] $ 5x mod 6 wird daraus
> -x $ [mm] \equiv [/mm] $ 5x $ [mm] \equiv [/mm] $ b mod 6, also -x $ [mm] \equiv [/mm] $ b mod 6.
Also die Aufgabe lautet in diesem Fall ja: 5x $ [mm] \equiv [/mm] $ b mod 6
Wir fangen an und sagen:
5 [mm] \equiv [/mm] -1 [mm] \pmod{6}, [/mm] diese Gleichung mutliplizieren wir mit x und erhalten
5x [mm] \equiv [/mm] -1x [mm] \pmod{6}, [/mm] die Gleichung kann ich auch schreiben als
-x [mm] \equiv [/mm] 5x [mm] \pmod{6} [/mm] (I)
so, und wie mache ich das jetzt weiter? verstehe irgendwie immer noch nicht deine schritte? also
-x $ [mm] \equiv [/mm] $ 5x $ [mm] \equiv [/mm] $ b (mod 6)....
weil ich kann ja 5x $ [mm] \equiv [/mm] $ b (mod 6) zu b $ [mm] \equiv [/mm] $ 5x (mod 6). Diese Gl. kann ich ja jetzt in (I) einsetzen und erhalte:
-x [mm] \equiv [/mm] b
aber wie kommste dann auf -x $ [mm] \equiv [/mm] $ 5x $ [mm] \equiv [/mm] $ b (mod 6)???
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:44 Do 09.06.2011 | | Autor: | abakus |
> entweder bin ich gerade bild, oder keine ahnung....
>
> > Deine Aufgabe lautete 5x [mm]\equiv[/mm] b mod 6.
> > Wegen -x [mm]\equiv[/mm] 5x mod 6 wird daraus
> > -x [mm]\equiv[/mm] 5x [mm]\equiv[/mm] b mod 6, also -x [mm]\equiv[/mm] b mod 6.
>
> Also die Aufgabe lautet in diesem Fall ja: 5x [mm]\equiv[/mm] b mod
> 6
>
> Wir fangen an und sagen:
>
> 5 [mm]\equiv[/mm] -1 [mm]\pmod{6},[/mm] diese Gleichung mutliplizieren wir
> mit x und erhalten
> 5x [mm]\equiv[/mm] -1x [mm]\pmod{6},[/mm] die Gleichung kann ich auch
> schreiben als
> -x [mm]\equiv[/mm] 5x [mm]\pmod{6}[/mm] (I)
>
> so, und wie mache ich das jetzt weiter? verstehe irgendwie
> immer noch nicht deine schritte? also
> -x [mm]\equiv[/mm] 5x [mm]\equiv[/mm] b (mod 6)....
>
> weil ich kann ja 5x [mm]\equiv[/mm] b (mod 6) zu b [mm]\equiv[/mm] 5x (mod
> 6). Diese Gl. kann ich ja jetzt in (I) einsetzen und
> erhalte:
>
> -x [mm]\equiv[/mm] b
>
> aber wie kommste dann auf -x [mm]\equiv[/mm] 5x [mm]\equiv[/mm] b (mod
> 6)???
Die Kongruenzrelation ist (als Äquivalenzrelation) transitiv. Wenn -x kongruent zu 5x und 5x kongruent zu b ist, dann ist auch -x kongruent zu b.
>
>
>
>
|
|
|
| |
|
Ok,
danke für die erklärung, dann hätte ich das verstanden. fehlt jetzt nur noch:
-x [mm] \equiv [/mm] 5x [mm] \equiv [/mm] b (mod 6)
ich sehe hier keine großen unterschied. ob da jetzt -x oder 5x, wie kann ich davon jetzt die lösung für x ablesen??
|
|
|
| |
|
Hallo steve.joke,
> danke für die erklärung, dann hätte ich das verstanden.
Gut. Das wirst Du noch öfter brauchen.
> fehlt jetzt nur noch:
>
> -x [mm]\equiv[/mm] 5x [mm]\equiv[/mm] b (mod 6)
>
> ich sehe hier keine großen unterschied. ob da jetzt -x
> oder 5x, wie kann ich davon jetzt die lösung für x
> ablesen??
1) Da ist ja auch kein Unterschied, jedenfalls soweit es die Modulrechnung betrifft.
2) Zum Ablesen ist der Unterschied dann aber doch riesig, zumal die Division in der Modulrechnung so ihre Tücken hat. Die Multiplikation ist da einfacher.
Wenn -x=b ist, dann ist x was?
Wenn [mm] -x\equiv b\mod{6} [/mm] ist, dann ist [mm] x=?\mod{6}
[/mm]
Grüße
reverend
|
|
|
|
