Erweiterter euk. Algorithmus < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:36 Di 12.02.2008 | | Autor: | crashby |
Hey Leute ,
Den einfachen normalen euklidischen Algorithmus habe ich verstanden.
nun gibt es ja folgende Formel beim erweiterten euk. Algorithmus
ggt(a,b)=s*a+t*b,
$ a,b $ sind natürliche Zahlen
s,t sind ganze Zahlen
Wenn ich also folgendes Beispiel habe:
$ ggt(32003,17) $
dann wende ich erstmal den euklidischen Algorithmus an und bekomme das hier:
$ 32003=1882*17+9 $
$ 17=9*1+8 $
$ 9=8*1+1 $
$ => ggt(32003,17)=1 $
Also habe ich folgende Darstellung:
$ 1=s*32003+t*17 $
Wie berechnet man jetzt s und $ t $?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:57 Di 12.02.2008 | | Autor: | abakus |
> Hey Leute ,
>
> Den einfachen normalen euklidischen Algorithmus habe ich
> verstanden.
>
>
> nun gibt es ja folgende Formel beim erweiterten euk.
> Algorithmus
>
> ggt(a,b)=s*a+t*b,
> [mm]a,b[/mm] sind natürliche Zahlen
> s,t sind ganze Zahlen
>
> Wenn ich also folgendes Beispiel habe:
> [mm]ggt(32003,17)[/mm]
>
> dann wende ich erstmal den euklidischen Algorithmus an und
> bekomme das hier:
>
> [mm]32003=1882*17+9[/mm]
> [mm]17=9*1+8[/mm]
> [mm]9=8*1+1[/mm]
>
> [mm]=> ggt(32003,17)=1[/mm]
>
> Also habe ich folgende Darstellung:
>
> [mm]1=s*32003+t*17[/mm]
>
> Wie berechnet man jetzt s und [mm]t [/mm]?
Die Gleichung ist eine lineare diophantische Gleichung mit unendlich vielen Lösungspaaren (s;t).
Ich denke, du müsstest dafür erstmal die lineare Kongruenz [mm] 32003*s\equiv1 [/mm] mod 17 lösen.
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:04 Do 21.02.2008 | | Autor: | unknown |
Moin,
am einfachsten geht das mit "rückwärts Einsetzten": Wenn
[mm] $\displaystyle [/mm] 32003 = [mm] 1882\cdot17 [/mm] + 9$,
[mm] $\displaystyle [/mm] 17 = [mm] 9\cdot1 [/mm] + 8$
und [mm] $\displaystyle [/mm] 9 = [mm] 8\cdot1 [/mm] + 1$.
Dann folgt aus der letzten Zeile $1 = 9 - [mm] 8\cdot1$ [/mm] und wegen $8 = 17 - [mm] 9\cdot1$ [/mm] (zweite Zeile) folgt weiter
[mm] $\displaystyle [/mm] 1 = 9 - (17 - [mm] 9\cdot1)\cdot1 [/mm] = [mm] 2\cdot9 [/mm] - [mm] 1\cdot17$
[/mm]
und schließlich wegen $9 = 32003 - [mm] 1882\cdot17$ [/mm] (erste Gleichung) erhältst Du
[mm] $\displaystyle [/mm] 1 = [mm] 2\cdot(32003 [/mm] - [mm] 1882\cdot17) [/mm] - [mm] 1\cdot17 [/mm] = [mm] 2\cdot32003 [/mm] - [mm] 3765\cdot17$.
[/mm]
Allgemein gilt: Wenn [mm] $\textstyle [/mm] a - q b = r$ und [mm] $\textstyle [/mm] s b + t r = d$ bekannt sind, dann ist
[mm] $\displaystyle [/mm] d = s b + t (a - q b) = t a + (s - q t) b$.
Damit kann man sich dann von unten nach oben hocharbeiten.
Hoffe, das hilft Dir.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:31 Fr 29.02.2008 | | Autor: | crashby |
Hi unknown,
danke sehr habe in der Klausur volle Punkte dafür bekommen also es hat mir sehr geholfen :)
lg crash
|
|
|
|
