
|
|
|
Autor |
Nachricht |
nixkönner Newbie


Anmeldungsdatum: 27.11.2007 Beiträge: 1
|
Verfasst am: 27 Nov 2007 - 11:36:28 Titel: Beweis zum ggT?! |
|
|
Ich bräuchte dringend jemanden, der mir helfen könnte folgendes zu beweisen:
ggT(ggT(a,b),b) = ggT(a,b)
Kann mir da jemand helfen?? |
|
 |
mkk Full Member


Anmeldungsdatum: 05.04.2005 Beiträge: 483
|
Verfasst am: 30 Nov 2007 - 12:09:35 Titel: |
|
|
Wie wäre es damit:
ggT(a,b) ≤ a gilt für alle a, b.
Also ist ggT(ggT(a,b),b) ≤ ggT(a,b) schon mal klar.
Andererseits folgt aus ggT(a,b) < x, daß entweder x nicht in der Teilermenge von a liegt oder x liegt nicht in der Teilermenge von b.
Das heißt, aus
ggT(ggT(a,b),b) < ggT(a,b)
würde folgen: ggT(a,b) teilt nicht ggT(a,b) (Widerspruch)
oder ggT(a,b) teilt nicht b (ebenfalls Widerspruch).
Also kann ggT(ggT(a,b),b) < ggT(a,b) nicht stimmen. Damit ist alles bewiesen. |
|
 |
Annihilator Valued Contributor


Anmeldungsdatum: 18.05.2007 Beiträge: 6394 Wohnort: (hier nicht mehr aktiv)
|
Verfasst am: 01 Dez 2007 - 13:46:50 Titel: |
|
|
Stichwort: Primfaktorzerlegung
Der ggT zweier Zahlen ist das Produkt aller gemeinsamer Primfaktoren der Zahlen. Wenn du dann den ggT dieses Produktes mit einer der beiden Ausgangszahlen ermitteltst, dann enthält das erste ggT natürlich schon alle Primfaktoren dieser Zahl. |
|
 |
cyrix42 Valued Contributor


 Anmeldungsdatum: 14.08.2006 Beiträge: 24257
|
Verfasst am: 01 Dez 2007 - 14:19:24 Titel: |
|
|
mkk hat folgendes geschrieben: |
Wie wäre es damit:
ggT(a,b) ≤ a gilt für alle a, b.
Also ist ggT(ggT(a,b),b) ≤ ggT(a,b) schon mal klar.
|
Die Schlussfolgerung ist falsch, denn die Funktion x->ggT(x,a) ist nicht monoton steigend in x:
ggT(7, =1<ggT(6, =2.
Cyrix |
|
 |
mkk Full Member


Anmeldungsdatum: 05.04.2005 Beiträge: 483
|
Verfasst am: 04 Dez 2007 - 12:34:49 Titel: |
|
|
cyrix42 hat folgendes geschrieben: |
mkk hat folgendes geschrieben: |
Wie wäre es damit:
ggT(a,b) ≤ a gilt für alle a, b.
Also ist ggT(ggT(a,b),b) ≤ ggT(a,b) schon mal klar.
|
Die Schlussfolgerung ist falsch, denn die Funktion x->ggT(x,a) ist nicht monoton steigend in x:
ggT(7, =1<ggT(6, =2.
Cyrix |
Daß das falsch ist, würde ich nicht sagen. Das Argument ist aber nicht die nicht vorhandene Monotonie, sondern: ggT(x,b) ist Teiler von x und als solcher natürlich kleiner oder gleich x.
D.h. ggT(x,b) ≤ x ist auf jeden Fall richtig.
Nun setze x = ggT(a,b).
Es folgt:
ggT(ggT(a,b),b) ≤ ggT(a,b)
ganz ohne Monotonie! |
|
 |
|
|
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|