| Autor |
Beitrag |
    
Bärchen
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 27. September, 2002 - 13:06: | 
|
Hilfe Hilfe Hilfe!!!!!
Bitte erklärt mir schnell wie ich einen
Aufsatz über kgV und ggT am besten
schreibe!!!!!! |
thuriferar783 (thuriferar783)
Erfahrenes Mitglied
Benutzername: thuriferar783
Nummer des Beitrags: 111
Registriert: 05-2002
| | Veröffentlicht am Freitag, den 27. September, 2002 - 19:15: |
|
Sind Multiplikation und Division in der Schule erst einmal eingeführt, so stellen sich auch bald die Aufgaben wie
Berechne den größten gemeinsamen Teiler (ggT) von 5 und 7, 6 und 12 und das kleinste gemeinsame Vielfache (kgV) von 2 und 3, 6 und 8 aus. Kurz erklärt sei, dass der ggT von zwei natürlichen Zahlen a und b die größte natürliche Zahl ist, die sowohl a als auch b teilt. Das kgV von a und b ist wiederum die kleinste natürliche Zahl, die sowohl von a also auch von b geteilt wird. So gilt zum Beispiel
ggT(5,7)=1, ggT(6,12)=6, kgV(2,3)=6 und kgV(6,8)=24. Sind die Zahlen klein, so kann man den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache meistens durch scharfes Hingucken bestimmen. Sind die Zahlen allerdings groß, so entstehen echte Schwierigkeiten, die aber wiederum in der Kryptographie ausgenutzt werden.
Einfache Algorithmen
Die einfachste (im Sinne von verständlich) Berechnung ist die jene über die Primfaktorzerlegung, die nach dem Fundamentalsatz der Arithmetik eindeutig ist (Die Basis der Mathematik). Widmen wir uns erst einmal dem ggT, so ist die Überlegung:
Gesucht ist eine Zahl, die a und b teilt. Also kann ihre Primfaktorzerlegung auch nur aus Zahlen bestehen, die sowohl als Primfaktoren in a und b vorkommen. Zweitens muss die Häufigkeit der Primfaktoren maximal gewählt werden, damit die Zahl, die größte ist. Nehmen wir a=36 und b=270, so gilt für die Primfaktorzerlegungen dieser beiden Zahlen: a=36=2²*3² und b=270=2*3³*5. Also hat der ggT die Primfaktoren 2 und 3 (5 kann nicht sein, da 5 nicht 36 teilt). Nun müssen noch die Exponenten bestimmt werden. Unter Berücksichtung der Teilbarkeit kann der Exponent von 2 maximal 1 ein (sonst teilt die Zahl 270 nicht) und der von 3 maximal 2 sein. Somit ist der größte gemeinsame Teiler von 36 und 270
ggT(36,270)=2*3²=18. Das kleinste gemeinsame Vielfache berechnet sich auf dieser Grundlage ähnlich. Hier wird allerdings jeder Primfaktor genommen, mit jeweils dem höchsten Exponenten, es gilt also
kgV(36,270)=2²*3³*5=540 Bei dieser Berechnung ist auffällig, dass die Berechnung sehr einfach wird, wenn a und b Primzahlen sind, denn dann gilt
ggT(a,b)=1 und kgV=(a,b)a*b. Die Berechnung des kleinsten gemeinsamen Teilers und größten gemeinsamen Vielfachen scheitern allerdings bei großen Zahlen an der Primfaktorzerlegung. Es gibt bis heute keinen effizienten Algorithmus, der sie berechnet, so dass sie gut für Verschlüsselungtechniken benutzt werden kann.
Der Euklidische Algorithmus
Einer der wohl bedeutendsten Zahlentheoretiker, Euklid, hat allerdings einen Algorithmus entwickelt, um en ggT zu berechnen, ohne die Primfaktoren direkt bemühen zu müssen. Das Schlagwort dieses Algorithmus ist Division mit Rest (z.B. 12:5=2*5+2, wobei 2 der Rest ist). Sind wieder a und b natürliche Zahlen und ohne Beschränkung der Allgemeinheit a>b, so ist der Algorithmus
1. Teile a durch b mittels Division mit Rest und erhalte Zahlen r und q, sodass gilt: a=b*q+r.
2. Ist r=0, so gilt ggT(a,b)=b.
3. Ist r ungleich 0, so führe i. aus mit a=b und b=r.
Dieser Algorithmus kann zwar sehr aufwändig werden, liefert aber nach endlichen vielen Schritten das Ergebnis.
Rechnen wir noch einmal das obige Beispiel durch, so ergeben sich folgende Schritte (a=270, b=36):
* 270=7*36+18, da 18 nicht 0 ist, setzen wir a=36 und b=18,
* 36=2*18+0, da der Rest nun Null ist, ergibt sich ggT(270,36)=18
Dies verifiziert das erste Ergebnis. Nun muss allerdings noch das kleinste gemeinsame Vielfache berechnet werden. Dies ist mit einer kleinen Formel, aber ganz einfach, denn es gilt
ggT(a,b)*kg(a,b)=a*b. In unserem Beispiel ergibt das
ggT(a,b)*kgV(a,b)=18*kgV(a,b)=ab=36*270=9720 -> kgV(a,b)=9720/18=540. Was wiederum dem obigen Ergebnis entspricht.
Neben der Faszination am Teiler finden, gibt es Anwendungen in der Zahlentheorie (Restklassenringe der ganzen Zahlen), in der Kryptographie (entschlüsseln) und in der Algebra.
(entnommen: http://freenet.meome.de/app/fn/artcont_portal_news_article.jsp/79883.html
Gruß, Oli P.
____________________________
Über ein Feedback und/oder konstruktive Kritik freue ich mich immer!
|
Bärchen
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 28. September, 2002 - 07:41: |
|
vielen Dank
Gruß Bärchen |
Bärchen
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 28. September, 2002 - 20:46: |
|
Wir hatten schon die Berechnung von kgv und ggt
eigentlich ,wollte ich nur einen kurzen Aufsatz
über das ggt und kgv verständlich erklärt
so dass es auch ein doofer versteht !!!!!! |
|
