Lösen einer Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:57 Mi 01.08.2012 | | Autor: | phineas |
| Aufgabe | Finden Sie alle ganzzahligen Lösungen der folgenden Kongruenzen:
(b) $133y = [mm] 280\, (mod\, [/mm] 91)$ |
Ich habe bereits einen Ansatz, kann mir aber nicht erklären wie ich auf die Lösungen modulo 91 kommen soll.
$133y [mm] \equiv 280\, (mod\, [/mm] 91)$
Durch Wahl geeigneter Repräsentanten kommt man zu
$42y [mm] \equiv 7\, (mod\, [/mm] 91)$
Danach bilde ich den $ggT(42, 91) = 7$ und kann a, b und m (Kongruenz der Form $ax=b [mm] \,(mod\, [/mm] m )$) durch 7 teilen:
$6y = [mm] 1\,(mod\,13)$
[/mm]
Durch Anwendung des Euklidischen Algorithmus ergibt sich
[mm] $13:6=2\,R1$
[/mm]
[mm] $6:1=2\,R1$
[/mm]
und
$1=13-2*6$
Daher muss [mm] $x_{0} \equiv 2\,(mod\,13)$ [/mm] sein.
Wie komme ich jetzt zu den Lösungen modulo 91?
Ich bin ursprünglich davon ausgegangen, eine Multiplikation mit b nach dem Teilen durch 7 brächte zumindest die erste Lösung modulo 91 (es gibt ja $ggt(42,91)=7$ Lösungen modulo 91), aber [mm] $2*1=2\,(mod\, [/mm] 91)$ ist wegen Rechenprobe definitv nicht richtig.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi,
> Finden Sie alle ganzzahligen Lösungen der folgenden
> Kongruenzen:
> (b) [mm]133y = 280\, (mod\, 91)[/mm]
> Ich habe bereits einen
> Ansatz, kann mir aber nicht erklären wie ich auf die
> Lösungen modulo 91 kommen soll.
> [mm]133y \equiv 280\, (mod\, 91)[/mm]
> Durch Wahl geeigneter
> Repräsentanten kommt man zu
> [mm]42y \equiv 7\, (mod\, 91)[/mm]
> Danach bilde ich den [mm]ggT(42, 91) = 7[/mm]
> und kann a, b und m (Kongruenz der Form [mm]ax=b \,(mod\, m )[/mm])
> durch 7 teilen:
> [mm]6y = 1\,(mod\,13)[/mm]
> Durch Anwendung des Euklidischen
> Algorithmus ergibt sich
> [mm]13:6=2\,R1[/mm]
> [mm]6:1=2\,R1[/mm]
> und
> [mm]1=13-2*6[/mm]
> Daher muss [mm]x_{0} \equiv 2\,(mod\,13)[/mm] sein.
> Wie komme ich jetzt zu den Lösungen modulo 91?
Da 1= 13-2*6 ist, ist [mm] x_{0} \equiv -2\,(mod\,13)\equiv 11\,(mod\,13). [/mm] Mit dem Teilen am Anfang ist das so ne Sache, wie hättest du denn durch 7 geteilt, wenn 42y [mm] \equiv 6\, (mod\, [/mm] 91) gewesen wäre?
Ich würde die Sache so angehen: 133y [mm] \equiv 280\, (mod\, [/mm] 91)
[mm] \gdw [/mm] 42y [mm] \equiv 7\, (mod\, [/mm] 91)
[mm] \gdw [/mm] 42y [mm] \equiv 7\, (mod\, [/mm] 13) und 42y [mm] \equiv 7\, (mod\, [/mm] 7) (, da 91=7*13)
[mm] \gdw [/mm] 3y [mm] \equiv 7\, (mod\, [/mm] 13) und 0y [mm] \equiv 0\,(mod\, [/mm] 7)
[mm] \gdw [/mm] 3y [mm] \equiv 7\, (mod\, [/mm] 13) , |*9
[mm] \gdw [/mm] 27y [mm] \equiv 63\, (mod\, [/mm] 13)
[mm] \gdw [/mm] y [mm] \equiv 11\, (mod\, [/mm] 13)
[mm] \IL=\{11+13z | z\in\IZ \}
[/mm]
Also statt teilen lieber immer mit dem Inversen multiplizieren.
Viele Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:37 Mi 01.08.2012 | | Autor: | phineas |
Vielen Dank, unglaublich das es nur am Vorzeichen lag, das ist fast schon peinlich. Jetzt macht auch Sinn, warum Kongruenzlöser mir 11 als Ergebnis liefern ($-2 [mm] \equiv 11\,(mod \,13)$). [/mm]
Zu meinem Lösungsansatz zum Vereinfachen der Gleichung durch Teilen von a,b,c durch $ggT(a, m)$: Ich kann zwar keinen Beweis antreten, aber mein Mathe-Skript besagt, falls $ggT(a,m)$ $b$ nicht teilen sollte (also $ggT(a,m)|b$ nicht gilt), dann hat die Kongruenz keine Lösung.
Auch wenn du keine Lösung modulo 91 angegeben hast, komme ich jetzt von allein drauf (du kannst mich dennoch korrigieren falls ich was falsch mache):
Nach [mm] $-2\equiv11\,(mod\,13)$ [/mm] wissen wir, dass die erste (!) Lösung modulo 91 [mm] $11*1=11\,(mod\,91)$ [/mm] sein muss. Als ggT hat sich $ggT(a,m)=ggT(42, 91)=7$ ergeben, d.h. 7 Lösung mod 91. Lösungen ergeben sich aus $x+13r$ mit [mm] $0\leq [/mm] x<7$. Also entspricht $x$ all jenen Zahlen, die kongruent zu $11, 24, 37, 50, 63, 76, 89$ modulo 91 sind.
|
|
|
| |
|
Hallo phineas,
> Nach [mm]-2\equiv11\,(mod\,13)[/mm] wissen wir, dass die erste (!)
> Lösung modulo 91 [mm]11*1=11\,(mod\,91)[/mm] sein muss. Als ggT hat
> sich [mm]ggT(a,m)=ggT(42, 91)=7[/mm] ergeben, d.h. 7 Lösung mod 91.
> Lösungen ergeben sich aus [mm]x+13r[/mm] mit [mm]0\leq x<7[/mm]. Also
> entspricht [mm]x[/mm] all jenen Zahlen, die kongruent zu [mm]11, 24, 37, 50, 63, 76, 89[/mm]
> modulo 91 sind.
Das ist richtig. Einfacher gibst Du die Lösung aber eben mit [mm] x\equiv 11\mod{13} [/mm] an, das ist ja das gleiche.
Grüße
reverend
|
|
|
|
