erweiterter Euklid < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:23 Do 08.01.2009 | | Autor: | kawu |
Wie genau berechne ich s und t bei ggT(a,b) = s*a + b*t ?
Ich habe da schon etwas gelesen von Matrizen die 1 und 0 enthalten aber so richtig verstehe ich da den zusammenhang nicht. Kann mir das hier jemand erklären?
lg, KaWu
|
|
| |
|
Das ist im ![[]](/images/popup.gif) Wiki-Artikel gut erklärt.
Probiers mal mit einem eigenen Beispiel aus, und wenns nicht klappt, dann poste Deine Rechnung hier.
Rückfragen natürlich auch.
lg,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:15 Do 08.01.2009 | | Autor: | kawu |
Ja, den Artikel habe ich auch schon gelesen. Nur leider hat er mir nocht weiter geholfen.
Ich komme nicht darauf, wie die einzelnen s und t in den einzelnen Schritten des Beispiels zu stande kommen :(
|
|
|
| |
|
Hallo kawu,
leduart hat Dir inzwischen ein Beispiel vorgerechnet. Ich nehme mal ein anderes mit den beiden Zahlen 147 und 91, ein bisschen Farbe und kurzen Erklärungen.
Hier erst einmal der euklidische Algorithmus:
[mm] 147=\blue{91}*\green{1}+\red{56}
[/mm]
[mm] \blue{91}=\red{56}*1+\green{35}
[/mm]
[mm] \red{56}=\green{35}*\blue{1}+21
[/mm]
[mm] \green{35}=21*\red{1}+\blue{14}
[/mm]
[mm] 21=\blue{14}*\green{1}+\red{7}
[/mm]
[mm] \blue{14}=\red{7}*2+\green{0}
[/mm]
Den kennst Du ja. Der ggT ist also [mm] \red{7}.
[/mm]
Nun gehst Du den Weg rückwärts und versuchst, die 7 zu behalten, aber die anderen Faktoren nach und nach durch größere zu ersetzen. Dazu fängst Du immer in der vorletzten Zeile an und gehst aufwärts.
Die vorletzte Zeile umgestellt nach dem "Rest" [mm] \red{7} [/mm] ist ja
[mm] \red{7}=21-\blue{14}*\green{1}
[/mm]
und die davor, wieder umgestellt nach dem "Rest" [mm] (\blue{14}):
[/mm]
[mm] \blue{14}=\green{35}-21*\red{1}
[/mm]
Diese setzt Du nun ein, so dass Du aus der Gleichung mit der [mm] \red{7} [/mm] die [mm] \blue{14} [/mm] ersetzen kannst durch größere Zahlen (das ist Dein Ziel, solange bis Du bei den beiden ursprünglichen angekommen bist!):
[mm] \red{7}=21-\overbrace{(\green{35}-21*\red{1})}^{=\blue{14}}*\green{1}=21*2-\green{35}
[/mm]
Noch eine Zeile höher/zurück, nach dem Rest umstellen:
[mm] 21=\red{56}-\green{35}*\blue{1}
[/mm]
einsetzen:
[mm] \red{7}=\overbrace{(\red{56}-\green{35}*\blue{1})}^{=21}*2-\green{35}=\red{56}*2-\green{35}*3
[/mm]
etc. - nach Rest auflösen:
[mm] \green{35}=\blue{91}-\red{56}*1
[/mm]
einsetzen:
[mm] \red{7}=\red{56}*2-\overbrace{(\blue{91}-\red{56}*1)}^{=\green{35}}*3=\red{56}*5-\blue{91}*3
[/mm]
endlich: erste Zeile nach Rest auflösen:
[mm] \red{56}=147-\blue{91}*\green{1}
[/mm]
einsetzen:
[mm] \red{7}=\overbrace{(147-\blue{91}*\green{1})}^{=\red{56}}*5-\blue{91}*3=147*\red{5}-\blue{91}*\red{8}
[/mm]
Also, jetzt nicht mehr so bunt:
[mm] \a{}7=147*5-91*8
[/mm]
Fertig.
Klarer?
Dann versuchs mal selbst hiermit: 144,104
Viel Erfolg!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:02 Fr 09.01.2009 | | Autor: | kawu |
Ich glaube, das Grundprinzip verstanden zu haben. Allerdings habe ich noch einen winzigen Fehler da drin:
ggT von 104 und 144:
1.: 144 = 1*104+40
2.: 104 = 2*40+24
3.: 40 = 1*24 + 16
4.: 24 = 1*16 + 8
5.: 16 * 2*8+0
ggT(144,104)=8
Nun der eEA:
8 = 24-16*1
16 = 40-24*1
8 = 24 - (40 - 24 * 1) * 1
24 = 104 - 2 * 40
8 = (104 - 2 * 40) - (40 - 24) = 104 - 3 * 40 + 24
40 = 144 - 104
104 - 3 * (144 - 104) + 24 = 8 = -3 * 144 + 4 * 104 + 24
Mit der 24 weiß ich nichts anzufangen, die Gleichung müsste doch s*a + t*b = ggT(a,b) lauten, oder nicht?
lg, KaWu
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:01 Fr 09.01.2009 | | Autor: | leduart |
Hallo
> Ich glaube, das Grundprinzip verstanden zu haben.
> Allerdings habe ich noch einen winzigen Fehler da drin:
>
> ggT von 104 und 144:
>
> 1.: 144 = 1*104+40
> 2.: 104 = 2*40+24
> 3.: 40 = 1*24 + 16
> 4.: 24 = 1*16 + 8
> 5.: 16 * 2*8+0
>
> ggT(144,104)=8
>
>
>
> Nun der eEA:
>
> 8 = 24-16*1
>
> 16 = 40-24*1
> 8 = 24 - (40 - 24 * 1) * 1
jetzt zusammenfassen oder an beiden Stellen 24 einsetzen nicht nur an einer!
8=2*24-1*40
> 24 = 104 - 2 * 40
> 8 = (104 - 2 * 40) - (40 - 24) = 104 - 3 * 40 + 24
>
> 40 = 144 - 104
> 104 - 3 * (144 - 104) + 24 = 8 = -3 * 144 + 4 * 104 + 24
>
>
> Mit der 24 weiß ich nichts anzufangen, die Gleichung müsste
auch hier könntest du noch deine Gleichung für 24 einsetzen!
> doch s*a + t*b = ggT(a,b) lauten, oder nicht?
ja!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:08 Fr 09.01.2009 | | Autor: | kawu |
blöder Fehler. :D Danke für den Tip!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:40 Fr 09.01.2009 | | Autor: | kawu |
Ich versuche gerade, mit dem eea das inverse Element von a = 5 [mm] $\in \mathds{F} [/mm] = [mm] \mathds{Z}_13 [/mm] = [mm] \{0,1,2,3,4,5,6,7,8,9,10,11,12\}$ [/mm] zu berechnen.
Nur bekomme ich nicht das heraus, was ich gerne hätte: 8
Zuerst berechne ich also den ggT von 13 und 5:
13=5*2+3
5=3*1+2
3=2*1+1
2=1*2+0
Dann kommt der eeA:
1=3-2*1
2=5-3*1
1=3-(5-3)
3=13-5*2
1=(13-5*2)-(5-(13-5*2))
Und dann? Dann komme ich nichtmehr weiter. damit weiß ich jetzt überhaupt nichts anzufangen.
|
|
|
| |
|
Jetzt musst Du doch nur noch die 5er zusammenfassen und die 13er auch:
> 1=(13-5*2)-(5-(13-5*2))
Also 1=13-2*5-5+13-2*5=2*13-5*5 (stimmt: 26-25=1)
Da Du [mm] \mod{13} [/mm] rechnest, kannst Du die 13er streichen und hast also stehen: [mm] -5*5\equiv 1\mod{13}. [/mm] Das Inverse von 5 ist also -5 ...
> Und dann? Dann komme ich nicht mehr weiter. damit weiß ich
> jetzt überhaupt nichts anzufangen.
... und [mm] -5\equiv [/mm] ? [mm] \mod{13}
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:15 Fr 09.01.2009 | | Autor: | kawu |
Was hast du da gemacht um auf 1=13-2*5-5+13-2*5=2*13-5*5 zu kommen?
|
|
|
| |
|
Hallo kawu,
> Was hast du da gemacht um auf 1=13-2*5-5+13-2*5=2*13-5*5 zu
> kommen?
>
Wie Du richtig gemacht hast, ist
[mm]\left(1\right) \ 13=2*5+3[/mm]
[mm]\left(2\right) \ 5=1*3+2[/mm]
[mm]\left(3\right) \ 3=1*2+1[/mm]
Daher ist ggt(13,5)=1.
Um jetzt eine Darstellung,
[mm]1=a*13+b*5[/mm]
mit [mm]a,b \in \IZ[/mm] zu finden, gehen wir wie folgt vor:
Aus Gleichung (3) erhalten wir:
[mm]1=1*3-1*2[/mm]
Ersetzen wir jetzt [mm]2=1*5-1*3[/mm] ( aus (2) ), so ergibt sich:
[mm]1=1*3-1*\left(1*5-1*3\right)=2*3-1*5[/mm]
Nun ersetzen wir [mm]3=13-2*5[/mm] ( aus (1) ):
[mm]1=2*3-1*5=2*\left(1*13-2*5\right)=2*13-5*5[/mm]
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:49 Do 08.01.2009 | | Autor: | leduart |
Hallo
Du hast den euklidschen alg. bis zum ggt gemacht. in der letzten Zeile steht der ggt.
du löst auf, ggt= dann ersetzt du jeweil durch die Zeile darüber,
Schreib mal ein Bsp. und sag, wo du nicht weiterkommst.
ein einfaches Bsp:
ggt(24,15)
I 24=1*15+ 9
II 15=1*9+6
III 9=1*6+3
IV 6=2*3
ggt=3
aus III 3=9-1*6
aus II 6=15-1*9 eingesetzt 3=9-(15+9)=-15+2*9
aus 1 9=24-1*15 eingesetzt 3=-15+2*(24-15)=2*24 -3*15
Gruss leduart
|
|
|
|
