ggT(a,b) Beweise < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:22 Di 11.10.2011 | | Autor: | Deztiny |
| Aufgabe | Zeigen Sie die Aussagen:
i.) Es ist ggT(a,b) = ggT(a,-b)
ii.) Ist b = 0, dann gilt ggT(a,b) = |a|
iii.) Ist b>0, und a = qb + r die Division von a durch b mit Rest r, dann gilt ggT(a,b) = ggT(b,r)
Da stets r < b gilt, werden in jedem Schritt von ii.) die Zahlen kleiner und man erhält einen endlichen Algorithmus zur Bestimmung des ggT, den sog. Euklidischen Algorithmus. |
Hallo!
Zunächst unsere (Unidefinition) vom ggT:
ggT(a,b) := max{c [mm] \in \IZ [/mm] | (c|a) [mm] \wedge [/mm] (c|b)}
zu i.) ggT(a,b) = ggT(a, -b)
[mm] \Rightarrow [/mm] c|a [mm] \wedge [/mm] c|b [mm] \Rightarrow [/mm] c|a [mm] \wedge [/mm] c|(-b) [mm] \Rightarrow [/mm] ggT(a,-b)
zu ii.) b = 0, und ggT(a,b) = |a|
[mm] \Rightarrow [/mm] c|a [mm] \wedge [/mm] c|b [mm] \Rightarrow [/mm] c|a [mm] \wedge [/mm] c|0 [mm] \Rightarrow [/mm] c|a [mm] \Rightarrow [/mm] c = |a| [mm] \Rightarrow [/mm] ggT(a,0) = |a|
zu iii.) (ist leider unvollständig, hier bräuchte ich hilfe!)
b>0 , a = qb + r [mm] \Rightarrow [/mm] ggT(a,b) = ggT (r,b) [mm] \Rightarrow [/mm] c|a [mm] \wedge
[/mm]
c|b [mm] \Rightarrow [/mm] ... ?
Danke schonmal und Gruß!
Dezt
P.S.:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
moin Deztiny,
> Zeigen Sie die Aussagen:
> i.) Es ist ggT(a,b) = ggT(a,-b)
> ii.) Ist b = 0, dann gilt ggT(a,b) = |a|
> iii.) Ist b>0, und a = qb + r die Division von a durch b
> mit Rest r, dann gilt ggT(a,b) = ggT(b,r)
>
> Da stets r < b gilt, werden in jedem Schritt von ii.) die
> Zahlen kleiner und man erhält einen endlichen Algorithmus
> zur Bestimmung des ggT, den sog. Euklidischen Algorithmus.
> Hallo!
>
> Zunächst unsere (Unidefinition) vom ggT:
>
> ggT(a,b) := max{c [mm] \in \IZ [/mm] | (c|a) [mm] \wedge [/mm] (c|b)}
>
> zu i.) ggT(a,b) = ggT(a, -b)
> [mm]\Rightarrow[/mm] c|a [mm]\wedge[/mm] c|b [mm]\Rightarrow[/mm] c|a [mm]\wedge[/mm] c|(-b)
> [mm]\Rightarrow[/mm] ggT(a,-b)
Du hast damit gezeigt: ist c ein Teiler von a und b so ist c auch ein Teiler von a und -b, aber hast du auch gezeigt, dass es sich in beiden Fällen um den größten gemeinsamen Teiler handelt?^^
> zu ii.) b = 0, und ggT(a,b) = |a|
> [mm]\Rightarrow[/mm] c|a [mm]\wedge[/mm] c|b [mm]\Rightarrow[/mm] c|a [mm]\wedge[/mm] c|0
> [mm]\Rightarrow[/mm] c|a [mm]\Rightarrow[/mm] c = |a| [mm]\Rightarrow[/mm] ggT(a,0) =
> |a|
auch hier fehlt die Tatsache, dass |a| der größte Teiler sein muss.
> zu iii.) (ist leider unvollständig, hier bräuchte ich
> hilfe!)
> b>0 , a = qb + r [mm]\Rightarrow[/mm] ggT(a,b) = ggT (r,b)
> [mm]\Rightarrow[/mm] c|a [mm]\wedge[/mm]
> c|b [mm]\Rightarrow[/mm] ... ?
Es ist a durch c teilbar, somit also auch qb + r.
Weiterhin ist b durch c teilbar, also auch qb.
Wie begründest du nun, dass r durch c teilbar ist?
Dann ist auch hier wieder der Punkt mit dem größten gemeinsamen Teiler zu klären, aber versuch das erstmal bei der i) und der ii).
> Danke schonmal und Gruß!
>
> Dezt
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:45 Di 11.10.2011 | | Autor: | Deztiny |
Zum Theme GRößter Teiler:
Ist sie das nicht nach Definition?
ggT(a,b) := max{c [mm] \in \IZ [/mm] | (c|a) [mm] \wedge [/mm] (c|b)}
Ich habe doch nur das genommen, was ich aus einer vordefinierten Definition weiß... und in dieser steht doch, dass ich mit diesem c [mm] \in \IZ [/mm] den maximalen Wert meine?
Wenn ich das so nicht machen kann, dann weiß ich leider auch nicht was genau noch fehlt, um zu zeigen, dass es der GRÖßTE Teiler ist. Könntest du mir da noch einen Tipp geben?
Zu Aufgabe iii.) Danke ich dir, ich melde mich morgen nochmal mit einer überarbeiteten Lösung :D (heute geh ich ins bett, morgen früh ist mein Mathekurs)
lg
Dezt
|
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> Zum Theme GRößter Teiler:
> Ist sie das nicht nach Definition?
>
> ggT(a,b) := max{c [mm]\in \IZ[/mm] | (c|a) [mm]\wedge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
(c|b)}
>
> Ich habe doch nur das genommen, was ich aus einer
> vordefinierten Definition weiß... und in dieser steht
> doch, dass ich mit diesem c [mm]\in \IZ[/mm] den maximalen Wert
> meine?
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Du meinst damit die größte Zahl, die a und b teilt.
Aber ob das auch die größte Zahl ist, die a und -b ist, steht bislang noch in den Sternen - diese Aussage ist Bestandteil dessen, was zu beweisen ist.
So könntest Du es machen:
Du könntest annehmen, daß der ggt von a und -b eine Zahl d ist, und dann zeigst Du, daß es nicht anders sein kann, als daß d=c ist.
Gruß v. Angela
>
> Wenn ich das so nicht machen kann, dann weiß ich leider
> auch nicht was genau noch fehlt, um zu zeigen, dass es der
> GRÖßTE Teiler ist. Könntest du mir da noch einen Tipp
> geben?
>
> Zu Aufgabe iii.) Danke ich dir, ich melde mich morgen
> nochmal mit einer überarbeiteten Lösung :D (heute geh ich
> ins bett, morgen früh ist mein Mathekurs)
>
> lg
> Dezt
|
|
|
|
