| Autor |
Beitrag |
    
Ronny (wonkyfox)
Neues Mitglied
Benutzername: wonkyfox
Nummer des Beitrags: 2
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 28. März, 2002 - 13:42: | 
|
Hi Leute
Der größte gemeinsame Teiler von a und b lässt sich als Linearkombination in der Form ggT(a,b)=x*a-y*b darstellen. Beispielsweise ist ggT(270,198)=3*270-4*198. Ich benötige einen Weg, das neben dem ggT auch die Koeffizienten x und y errechnet.
Wäre für eine hilfe dankbar
Ronny |
Lord Kuno
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 28. März, 2002 - 16:19: |
|
Das ist überhaupt kein Problem, dies funktioniert mit dem sogenannten erweiterten euklidischen Algorithmus (EEA). Ich erklär es am besten an deinem Beispiel:
Abkürzung: gcd für größter gemeinsamer Teiler!
Gesucht sind Zahlen x,y mit gcd(270,198) = 270x+198y.
I Runterrechnen!
270 = 1*198 + 72
198 = 2*72 + 54
72 = 1*54 + 18
54 = 3*18 + 0
Der letzte von 0 verschiedene Rest (die Zahl über 0), also die 18, ist der gcd.
II Hochrechnen!
Von der 18 ausgehend wird von unten nach oben in die Gleichungen eingesetzt.
}18 = 72 - 1*54
= 72 - 1*(198-2*72(
= 72 - 198 + 2*72
= 3*72 - 198
= 3*(270 - 1*198) - 198
= 3*270 - 3*198 - 198
= 3*270 - 4*198
|
Ronny (wonkyfox)
Neues Mitglied
Benutzername: wonkyfox
Nummer des Beitrags: 3
Registriert: 10-2000
| | Veröffentlicht am Freitag, den 29. März, 2002 - 21:36: |
|
Danke Dir!
Ronny |
|
