Ganzzahlige Lösung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:58 Sa 26.01.2013 | | Autor: | Fatih17 |
| Aufgabe | Bestimmen Sie die kleinste positive ganze Zahl x [mm] \in \IZ [/mm] so dass gilt:
7x [mm] \equiv [/mm] 2 (mod 37) und 5x [mm] \equiv [/mm] 7 (mod 33) |
Hallo liebe Gemeinde,
ich habe Versucht zu lösen, aber irgendwo habe ich einen Fehler:
1.Schritt:
Umschreiben und die x auf Gleichheit bringen:
7x = 2 + 37k
5x = 7 + 33m
45x =10 + 185k
45x =49 + 231m
2.Schritt: Formel aufstellen:
10+185k = 49+231m
[mm] \gdw [/mm] 185k-231m =39
3.Schritt: Berlekamp Algorithmus durchführen:
[mm] \vmat{ q & d & a' & b' \\ - & 185 & 1 & 0 \\ - & -231 & 0 & 1 \\ -4 & 1 & 5 & 4 \\ }
[/mm]
4.Schritt: In die Formeln einsetzen:
Ich habe folgende Formeln:
k= c * [mm] x_{0} [/mm] + [mm] \beta [/mm] * l
m=c * [mm] y_{0} [/mm] - [mm] \alpha [/mm] * l
wobei c=39 , [mm] x_{0}=5 [/mm] , [mm] y_{0}=4 [/mm] , [mm] \alpha [/mm] = 185 und [mm] \beta [/mm] = -231
jetzt habe ich heraus:
k=195 - 231l
Als ich bei Wolfram Alpha mal nachgeschaut habe, hatte er 195 + 231l heraus. Wo liegt mein Fehler?
Vielen Dank im voraus
MFG
Fatih
|
|
| |
|
Hallo Fatih,
Du möchtest den chinesischen Restsatz anwenden.
> Bestimmen Sie die kleinste positive ganze Zahl x [mm]\in \IZ[/mm] so
> dass gilt:
>
> 7x [mm]\equiv[/mm] 2 (mod 37) und 5x [mm]\equiv[/mm] 7 (mod 33)
> Hallo liebe Gemeinde,
>
> ich habe Versucht zu lösen, aber irgendwo habe ich einen
> Fehler:
>
> 1.Schritt:
>
> Umschreiben und die x auf Gleichheit bringen:
Na, erstmal stellen wir fest, dass [mm] \ggT{(33,37)}=1 [/mm] ist.
Dann gehts weiter.
> 7x = 2 + 37k
> 5x = 7 + 33m
(Nebenbei: unter Anwendung von Inversen können wir hier auch schreiben
$x=2*16+37k'$
$x=7*20+33m'$)
> 45x =10 + 185k
> 45x =49 + 231m
Hm. Das wars wohl schon. $5*7=35$. Also stehen links jeweils 35x.
> 2.Schritt: Formel aufstellen:
Allerdings fällt durch das Gleichsetzen hier die fehlerhafte Zahl ja wieder weg.
> 10+185k = 49+231m
> [mm]\gdw[/mm] 185k-231m =39
>
> 3.Schritt: Berlekamp Algorithmus durchführen:
>
> [mm]\vmat{ q & d & a' & b' \\
- & 185 & 1 & 0 \\
- & -231 & 0 & 1 \\
-4 & 1 & 5 & 4 \\
}[/mm]
Hier solltest Du besser noch ein paar Zwischenschritte angeben. Wie gehts weiter?
> 4.Schritt: In die Formeln einsetzen:
>
> Ich habe folgende Formeln:
>
> k= c * [mm]x_{0}[/mm] + [mm]\beta[/mm] * l
> m=c * [mm]y_{0}[/mm] - [mm]\alpha[/mm] * l
>
> wobei c=39 , [mm]x_{0}=5[/mm] , [mm]y_{0}=4[/mm] , [mm]\alpha[/mm] = 185 und [mm]\beta[/mm] =
> -231
>
> jetzt habe ich heraus:
>
> k=195 - 231l
>
> Als ich bei Wolfram Alpha mal nachgeschaut habe, hatte er
> 195 + 231l heraus. Wo liegt mein Fehler?
Sieht so auf Anhieb nach [mm] \beta [/mm] aus, aber ich habs nicht nachgerechnet. Da war ja nichts zum Nachrechnen. 
Grüße
reverend
PS: Die gesuchte Lösung ist [mm] 1031\mod{(33*37)}. [/mm] Ich nehme an, dass Du das schon weißt, aber eben noch den Weg zeigen musst, oder?
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 23:41 Di 05.02.2013 | | Autor: | Fatih17 |
Guten Abend nochmal,
es geht mir eher darum, woher ich genau weiß, wann ich [mm] \alpha [/mm] , [mm] \beta [/mm] , x0 , y0 bestimmen muss.
Ich habe folgendes bemerkt:
Bei Gleichungen wie diesen:
87x - 98y = -31
87*(-9) - 98*(-8) = 1
komme ich auf ein korrekte Ergebnis, wenn ich:
[mm] \alpha [/mm] = zweite Zahl, [mm] \beta [/mm] = erste Zahl , x0 =-8, y0=-9 wähle!
Bei solchen Gleichungen:
121x+112y=-23
121*25+112*(-27) =1
muss ich:
[mm] \alpha [/mm] = erste Zahl, [mm] \beta [/mm] = zweite Zahl , x0 =25, y0=-27 wählen!
Heißt:
Ich habe keine Gemeinsamkeit gefunden, wo ich konkret sagen kann, welches immer [mm] \alpha [/mm] und welches immer [mm] \beta [/mm] ist ...
MFG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Fr 08.02.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
