Erw. euklidischer Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo liebe Leute,
habe den EA und den EEA verstanden und auch schon implementiert. Allerdings habe ich bei den formalen Beweisen Probleme.
Muss zu [mm] (n,m) \in \IN \times \IN_0 [/mm] beweisen, dass
[mm] ggt(n,m) = min( \{nx+my | x,y \in \IZ \} \cap \IN ) [/mm]
Hat jemand einen Tipp für mich? Wäre super!
LG Janine
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:35 So 07.05.2006 | | Autor: | felixf |
Hallo Janine!
> habe den EA und den EEA verstanden und auch schon
> implementiert. Allerdings habe ich bei den formalen
> Beweisen Probleme.
>
> Muss zu [mm](n,m) \in \IN \times \IN_0[/mm] beweisen, dass
>
> [mm]ggt(n,m) = min( \{nx+my | x,y \in \IZ \} \cap \IN )[/mm]
>
> Hat jemand einen Tipp für mich? Wäre super!
Einmal musst du zeigen, dass der groesste gemeinsame Teiler von $n$ und $m$ in der Menge [mm] $\{nx+my \mid x,y \in \IZ \}$ [/mm] auftaucht. Das bekommst du im Prinzip aus dem Beweis des EEA.
Dann gehst du wie folgt vor: Sind $x, y [mm] \in \IZ$, [/mm] dann ist $n x + m y$ durch den ggT von $n$ und $m$ teilbar. Ist also $n x + m y [mm] \in \IN$, [/mm] so gilt $ggT(n, m) [mm] \le [/mm] n x + m y$.
Siehst du es jetzt?
LG Felix
|
|
|
| |
|
Hallo Felix,
vielen lieben Dank für deine Hinweise - das hat mir sehr geholfen. Habe mir deine Vorgehensweise verinnerlicht und mich dann nochmal intensiv damit beschäftigt. Jetzt werde ich mich ans formale Niederschreiben machen. Nachmals vielen Dank!!
Liebe Grüße, Janine
|
|
|
|
