Kongruenzsystem < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man löse das Kongruenzsystem
3x [mm] \equiv [/mm] 12(8)
2x [mm] \equiv [/mm] 4(18)
35x [mm] \equiv [/mm] 10(30) |
Die Lösung und Herangehensweise der Aufgabe ist soweit klar. Bisher habe ich folgendes gemacht:
3x [mm] \equiv [/mm] 12(8)
x [mm] \equiv [/mm] 4(8)
2x [mm] \equiv [/mm] 4(18)
[mm] x\equiv [/mm] 2(18)
35x [mm] \equiv [/mm] 10(30)
35x [mm] \equiv [/mm] 70(30)
x [mm] \equiv [/mm] 2(30)
ggt(8,18,30) = 2
ggt(8,18) = 2
ggt(18,30) = 2
ggt(8,30) = 2 [mm] \to [/mm] lösbar
M= m1 *m2 *m3 = 8*18*30= 4320
[mm] \bruch{4320}{8} [/mm] y1 + [mm] \bruch{4320}{18} [/mm] y2 + [mm] \bruch{4320}{30} [/mm] y3 = 1
540 y1 + 240 y2 + 144 y3 = 1
Nun komme ich nicht weiter. Eigentlich müsste ich die Gleichungssysteme
540 y1 [mm] \equiv [/mm] 2(8)
240 y2 [mm] \equiv [/mm] 2(18)
144 y3 [mm] \equiv [/mm] 2(30)
lösen.
Doch das geht nicht. Was muss ich tun?
Danke für die Hilfe.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:14 Di 21.10.2008 | | Autor: | abakus |
> Man löse das Kongruenzsystem
>
> 3x [mm]\equiv[/mm] 12(8)
> 2x [mm]\equiv[/mm] 4(18)
> 35x [mm]\equiv[/mm] 10(30)
> Die Lösung und Herangehensweise der Aufgabe ist soweit
> klar. Bisher habe ich folgendes gemacht:
>
> 3x [mm]\equiv[/mm] 12(8)
> x [mm]\equiv[/mm] 4(8)
>
>
> 2x [mm]\equiv[/mm] 4(18)
> [mm]x\equiv[/mm] 2(18)
Das ist falsch.
Aus ac [mm] \equiv [/mm] bc (m)
folgt a [mm] \equiv [/mm] b [mm] (\bruch{m}{ggt(c;m)})
[/mm]
Hier konkret: ggT(2;18)=2 ; 18:2=9
also [mm]x\equiv[/mm] 2(9)
>
> 35x [mm]\equiv[/mm] 10(30)
Beide Seiten durch 5 teilbar, ggT(5;30)=5 ; 30:5=6
7x [mm]\equiv[/mm] 2(6), und wegen 6x [mm] \equiv [/mm] 0(6) folgt daraus
[mm] 7x-6x\equiv [/mm] x [mm] \equiv [/mm] 2(6),
x [mm] \equiv [/mm] 2(6),
Gruß Abakus
> 35x [mm]\equiv[/mm] 70(30)
> x [mm]\equiv[/mm] 2(30)
>
> ggt(8,18,30) = 2
> ggt(8,18) = 2
> ggt(18,30) = 2
> ggt(8,30) = 2 [mm]\to[/mm] lösbar
>
> M= m1 *m2 *m3 = 8*18*30= 4320
>
> [mm]\bruch{4320}{8}[/mm] y1 + [mm]\bruch{4320}{18}[/mm] y2 + [mm]\bruch{4320}{30}[/mm]
> y3 = 1
>
> 540 y1 + 240 y2 + 144 y3 = 1
>
> Nun komme ich nicht weiter. Eigentlich müsste ich die
> Gleichungssysteme
>
> 540 y1 [mm]\equiv[/mm] 2(8)
>
> 240 y2 [mm]\equiv[/mm] 2(18)
>
> 144 y3 [mm]\equiv[/mm] 2(30)
>
> lösen.
> Doch das geht nicht. Was muss ich tun?
>
> Danke für die Hilfe.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
>
>
|
|
|
| |
|
ok, danke.
Aber wie mache ich nun weiter?
ich habe quasi:
x $ [mm] \equiv [/mm] $ 4(8)
[mm] x\equiv [/mm] 2(9) und
x $ [mm] \equiv [/mm] $ 2(6)
Nun muss ich den ggt finden!?? d.h.:
ggt(8,9,6) = 1
ggt(8,9) = 1
ggt(9,6) = 3
ggt(8,6) = 2
D.h. das Kongruenzsystem ist nicht lösbar, weil der ggt nicht gleich ist???
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:17 Di 21.10.2008 | | Autor: | abakus |
> ok, danke.
> Aber wie mache ich nun weiter?
>
> ich habe quasi:
>
> x [mm]\equiv[/mm] 4(8)
>
> [mm]x\equiv[/mm] 2(9) und
>
> x [mm]\equiv[/mm] 2(6)
>
> Nun muss ich den ggt finden!?? d.h.:
>
> ggt(8,9,6) = 1
> ggt(8,9) = 1
> ggt(9,6) = 3
> ggt(8,6) = 2
>
> D.h. das Kongruenzsystem ist nicht lösbar, weil der ggt
> nicht gleich ist???
>
>
Was willst du mit den ggT's?
Aus deinen 3 Äquivalenzaussagen folgen drei Gleichungen mit 4 Unbekannten:
(1) x=8k+4
(2) x=9m+2
(3) x= 6n+2 (wobei k, m, n [mm] \in \IZ [/mm] )
In diesem Gleichungssystem kannst du zwei der drei Variablen k, m, n beseitigen und erhältst x in Abhängigkeit von einer Variablen.
Mit etwas Übersicht geht es auch schneller.
Aus (2) und (3) folgt, dass x bei Teilung durch 18 den Rest 2 lässt, also [mm] x\in [/mm] { ..., -16; 2; 20; 38; 56; 74; 92;...}
Davon lassen ...;20; 92; ... den Rest 4 bei Teilung durch 8. Da all diese Lösungen den Abstand 72 besitzen, sind sie in der Form
x=72k+20 darstellbar.
Gruß Abakus
|
|
|
|
