|
|
|
|
| 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.
|
|
Home
FAQ
Regeln
Suchen
Registrieren
Login
