ggT und kgV < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:21 Mo 16.10.2006 | | Autor: | Xnyzer |
| Aufgabe | | Wie berechnet man den ggT und das kgV? |
Kann mir noch mal jemand sagen, wie man den ggT und das kgV berechnet? Bitte nicht mit irgendwelchem ausprobieren sondern einen richtigen Algorithmus bzw. Formel.
Vielen Dank!
(Wusste das schon mal, aber habe es leider wieder vergessen :§)
|
|
| |
|
Hi Xnyzer,
der ggT kann mit Hilfe des euklidischen Algorithmus bestimmt werden. Der Algorithmus liefert zu gegebenen m, n [mm] \in \IN, [/mm] m [mm] \ge [/mm] n, den größten gemeinsamen Teiler ggT(m,n).
1. Teile m durch n und bestimme den Rest r (d.h. bestimme r, so daß gilt m = q*n+r, wobei q, r [mm] \in \IZ, [/mm] 0 [mm] \le [/mm] r < n).
2. Falls r = 0 gilt bis du fertig und das Ergebnis ist der Wert von n.
3. Andernfalls: Setze m := n, n := r und fahre mit Schritt 1 fort.
Beispiel:
m = 816, n = 294
816 = 2*294 + 228
294 = 1*228 + 66
228 = 3*66 + 30
66 = 2*30 + 6
30 = 5*6 + 0
ggT(816,294) = 6
Daraus kannst du jetzt auch das kgV bestimmen, es gilt:
ggT(m,n) * kgV(m,n) = m * n
|
|
|
|
