Euklidischer Algorthmus(ggT) < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:46 Mi 01.11.2006 | | Autor: | Tommylee |
Hallo ,
wir müssen folgendes zeigen :
für a,b [mm] \in \IN [/mm] sein M(a,b) := {ax + by : x,y [mm] \in \IZ [/mm] }
Nun sollen wir zeigen :
1 [mm] \in [/mm] M(a,b) [mm] \gdw [/mm] ggT(a,b) = 1
Die eine Richtung ist klar :
ggT(a,b) = 1 [mm] \Rightarrow 1\in [/mm] M(a,b)
weil : weil : [mm] \forall [/mm] a,b [mm] \in \IN \exists [/mm] x,y [mm] \Rightarrow [/mm] ggT(a,b) = ax + by
Die andere Richtung krieg ich nicht hin :
zu zeigen also auch :
[mm] 1\in [/mm] M(a,b) [mm] \Rightarrow [/mm] ggT(a,b) = 1
Versuch einer Folgerung :
[mm] 1\in [/mm] M(a,b) [mm] \Rightarrow \exists [/mm] x,y [mm] \in \IZ \Rightarrow [/mm] ax + by = 1
aus ax + by = 1 [mm] \Rightarrow [/mm] .................. [mm] \Rightarrow [/mm] ggT (a,b) = 1
Ich muss jetzt auf ....... kommen . Hätte jemand eine Tip , der vielleicht
bei mir einen Klick auslöst ?
Vielen Dank für Eure Hilfe
bis dann
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:56 Mi 01.11.2006 | | Autor: | Hanno |
Hallo Tommy!
Überlege dir, dass jedes Element aus $M$ Vielfaches des ggT von $a$ und $b$ sein muss. Wenn der ggT also größer $2$ ist, dann kann die $1$ nicht in $M$ enthalten sein.
Allgemein ist das betragsmäßig kleinste Element in $M$ genau der $ggT$ von $a$ und $b$. Wenn du magst, kannst du ja mal versuchen, das zu beweisen.
Liebe Grüße,
Hanno
|
|
|
|
