Beweis: ggT(a,b)=ggT(a,a+b) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:42 So 20.03.2011 | | Autor: | sven__ |
| Aufgabe | | Man zeige: ggT(a, b) = ggT(a, a+b) |
d|a [mm] \wedge [/mm] d|b [mm] \Rightarrow \bruch{a}{d} \in \IZ \wedge \bruch{b}{d} \in \IZ \Rightarrow \bruch{a+b}{d} \in \IZ \Rightarrow [/mm] d|(a+b). Soweit so gut. Aber wie zeige ich, dass eben jenes d auch der größte Teiler ist bzw. der ggT von a und b gleich dem ggT von a und a+b ist?
mfG Sven
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.matheboard.de/thread.php?threadid=450007
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:58 So 20.03.2011 | | Autor: | Lippel |
Morgen Sven,
> Man zeige: ggT(a, b) = ggT(a, a+b)
> d|a [mm]\wedge[/mm] d|b [mm]\Rightarrow \bruch{a}{d} \in \IZ \wedge \bruch{b}{d} \in \IZ \Rightarrow \bruch{a+b}{d} \in \IZ \Rightarrow[/mm]
> d|(a+b). Soweit so gut. Aber wie zeige ich, dass eben jenes
> d auch der größte Teiler ist bzw. der ggT von a und b
> gleich dem ggT von a und a+b ist?
Es gelte: $d = [mm] ggT(a,b)\:$. [/mm] Angenommen es gilt $c = [mm] ggT(a,a+b)\:$ [/mm] und $c > d$.
Du weißt dann: $c [mm] \:|\:a$ [/mm] und $c [mm] \:|\: [/mm] a+b [mm] \Rightarrow \frac{a}{c}=m, \frac{a+b}{c}=n$ [/mm] mit $m,n [mm] \in \IZ \Rightarrow \frac{b}{c} [/mm] = [mm] \frac{a+b-a}{c} [/mm] = [mm] \frac{a+b}{c}+\frac{a}{c} [/mm] = n+m [mm] \in \IZ \Rightarrow [/mm] c [mm] \:|\: [/mm] b$
Damit teilt [mm] $c\:$ [/mm] sowohl [mm] $a\:$ [/mm] als auch [mm] $b\:$, [/mm] und es gilt $c > [mm] d=ggT(a,b)\:$. [/mm] Das ist ein Widerspruch, also kann es ein solches [mm] $c\:$ [/mm] nicht geben. Also ist bereits [mm] $d=ggT(a,a+b)\:$.
[/mm]
LG Lippel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:17 So 20.03.2011 | | Autor: | sven__ |
Hallo Lippel. Danke für deine Antwort. Allerdings kann ich den Widerspruch nicht entdecken. Warum kann es ein solches c nicht geben?
mfG Sven
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:21 So 20.03.2011 | | Autor: | Lippel |
[mm] $c\:$ [/mm] würde ja [mm] $a\:$ [/mm] und [mm] $b\:$ [/mm] teilen, wäre also eine gemeinsamer Teiler von [mm] $a\:$ [/mm] und [mm] $b\:$, [/mm] aber größer als der größte gemeinsame Teiler. Ein gemeinsamer Teiler kann aber natürlich nicht echt größer als der größte gemeinsame Teiler sein, denn damit wäre dieser nicht mehr der größte.
LG Lippel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:25 So 20.03.2011 | | Autor: | sven__ |
Ich glaube, jetzt hab ichs. Danke!
|
|
|
|
