ggT: "alternativer" Rechenweg? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:33 So 09.11.2008 | | Autor: | kawu |
Hallo liebe Zahlentheoretiker,
Ich würde gerne den ggT von zwei Zahlen in meinem Taschenrechner ausrechnen, kann deswegen diesen Algorithmus von Euklid (http://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler_und_kleinstes_gemeinsames_Vielfaches#Euklidischer_und_steinscher_Algorithmus) in seiner 'traditionellen Form' nicht verwenden weil das Teilen so mit Kommazahlen enden würde.
Ich habe mal von einer Gleichung gelesen: a = q * b + r
Kann mir mal jemand an einem Beispiel erklären, wie ich so den ggT (wenn ich da nicht etwas verwechselt habe) von z.B. 40 und 25 errechnen kann?
lg, kawu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:23 So 09.11.2008 | | Autor: | Fry |
Hi,
also das Prinzip ist folgendermaßen.
Also angenommen du möchtest ggT(a,b) mit a>b bestimmen.
Dann teilst du a durch b (Divison mit Rest):
a = q*b + r
Jetzt wiederholst du die Division, indem du b durch Rest teilst.
Dies machst du solange, bis du den Rest null hast.
Beispiel:
40 =1*25+15
25=1*15+10
15=1*10+5
10=2*5+0
[mm] \Rightarrow [/mm] ggT(40,25)=5
LG
Christian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:21 Mo 10.11.2008 | | Autor: | Fry |
...
|
|
|
|
