Euklidischer Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:35 Mo 26.10.2009 | | Autor: | durden88 |
| Aufgabe | | Seien n [mm] \ge [/mm] 1 und m [mm] \ge [/mm] 1 natürliche Zahlen. Beweisen Sie, dass ganze Zahlen x und y existieren, sodass n*x+m*y= ggt (n,m) gilt. |
Also ich habe gehört ich sollte einfach den Euklidischen Algorithmus rückwärts anwenden, nur wie? Man könnte es auch mit Induktion machen, aber den Euklidischen Algorithmus habe ich so gut verstanden, würde das gerne auf diesen Wege machen danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:15 Mo 26.10.2009 | | Autor: | pelzig |
Naja, wenn du den euklidischen Algorithmus für zwei Zahlen [mm] $z_2
[tex]\begin{equationarray}z_1=a_1\cdot z_2+z_3\\z_2=a_2\cdot z_3+z_4\\\vdots\\z_{n-1}=a_{n-1}\cdot z_n+z_{n+1}\\z_n=a_n\cdot z_{n+1}+1\end{equationarray}[/tex]
Nun schau dir die letze Gleichung an, da steht: 1 ist eine [mm] $\IZ$-Linearkombination [/mm] von [mm] $z_n$ [/mm] und [mm] $z_{n+1}$. [/mm] In der vorletzten Zeile steht: [mm] $z_{n+1}$ [/mm] ist eine [mm] $\IZ$-Linearkomb. [/mm] von [mm] $z_{n-1}$ [/mm] und [mm] $z_n$, [/mm] also ist 1 eine linearkombination von [mm] $z_n$ [/mm] und [mm] $z_{n-1}$. [/mm] Auf diese Weise steigst du immer weiter nach oben auf und erhälst schließlich: 1 ist eine [mm] $\IZ$-LK [/mm] von [mm] $z_2$ [/mm] und [mm] $z_1$, [/mm] q.e.d.
Das ist natürlich kein Beweis, aber die Idee sollte trotzdem rübergekommen sein.
Gruß, Robert
|
|
|
|
