GgT bei Euklid. Algorithmus < Klassen 8-10 < Schule < Mathe < Vorhilfe
|
Hallo,
also,...nach Anwendung des EA bekommt man ja einen größten gemeinsamen Teiler.
Als schnelles Beispiel,... gesucht wird der ggT von 969 und 627.
969=1·627+342
627=1·342+285
342=1·285+57
285=5·57+0 [mm] \Rightarrow [/mm] ggT ist also 57.
Warum funktioniert dieses Verfahren? Oder anders,..warum ist die 57 der ggT von 969, 627, 342 und 285 ... gibts da ne Erklärung für?
Bin für jede Idee dankbar.. :o)
Mark
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo oldpigweed!
> Als schnelles Beispiel,... gesucht wird der ggT von 969
> und 627.
> 969=1·627+342
> 627=1·342+285
> 342=1·285+57
> 285=5·57+0 [mm]\Rightarrow[/mm] ggT ist also 57.
>
> Warum funktioniert dieses Verfahren? Oder anders,..warum
> ist die 57 der ggT von 969, 627, 342 und 285 ... gibts da
> ne Erklärung für?
Sicher gibt es da eine Erklärung für... Warum der Algo so funktioniert, kann ich dir im Moment nicht sagen, vielleicht findest du bei Wikipedia etwas? Aber warum das der ggT ist, kann ich dir sagen: und zwar kann man das per Hand rechnen, indem man beide Zahlen in Primfaktoren zerlegt: 969=3*17*19 und 627=3*11*19. Und da siehst du, dass die Teiler 3 und 19 Teiler von beiden Zahlen sind, also ist der ggT das Produkt von diesen beiden. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Huhu Bastiane,
also erstmal Danke für die schnelle Antwort und verständliche Erklärung.
Habe das hier noch im Netz gefunden und werd nich schlau draus ..
"... Es sei a=q*b + r.
Dann ist jeder gemeinsame Teiler von a und b auch gemeinsamer Teiler von b und r. Denn wegen a=q*b + r gilt a-q*b = r und wenn eine Zahl die linke Seite dieser Gleichung teilt, so muss sie auch die rechte Seite teilen.
Umgekehrt: Jeder gemeinsame Teiler von b und r teilt auch a wegen a=q*b+r.
a und b haben also dieselben gemeinsamen Teiler wie b und r.
Also Ta∩Tb = Tb∩Tr und daher auch ggT(a,b)=ggT(b,r).
Anwendungs-Beispiel
Es gilt zum Beispiel, dass der ggT von 96 und 36 derselbe ist, wie der von 36 und 24, weil 96 beim Teilen durch 36 den Rest 24 lässt. Jetzt können wir die Zahlen 36 und 24 als unsere neuen Zahlen a und b nehmen und von vorne beginnen. Insgesamt erhalten wir so den euklidischen Algorithmus:
96 = 2·36+24
36 = 1·24+12
24 = 2·12+0
Also gilt ggT(96,36)=ggT(36,24)=ggT(24,12)=ggT(12,0).
Und da 12 die 0 teilt, folgt ggT(96,36)=ggT(12,0)=12. Also ggT(96,36)=12. "
Öhemm,...tja,..also ...vielleicht könnte das ja noch Jemand aufdröseln..?
Mark
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:38 Mi 28.02.2007 | | Autor: | leduart |
Hallo
Der Clou an der Sache ist, dass man dran denken muss: Wenn 2 Zahlen durch dieselbe Zahl teilbar sind, dann ist auch ihre Differenz durch die Zahl teilbar!
Also Dein Beispiel gesucht die Zahl z die 969 und 627 teilt
wenn sie die 2 teilt, dann auch die Differenz also 342
also such ich z was 627 und 342 teilt, wenns die Teilt dann auch die Differenz also 285.
z muss 342 und 285 teilen, also auch 57
57 teilt 285 und sich, und jetzt kannst du wieder rueckwaerts gehen, ..dann teilt es auch die Summe
Du kannst also hinten anfangen und immer sagen teilt das eine und das andere, deshalb auch die Summe,
Oder so wie ich vorne anfangen. und immer die Differenzen;
Das Verfahren ist sehr gut und nuetzlich, denn richtig grosse Zahlen in Primfaktoren zerlegen wird sehr langwierig.
und jetzt weiss ich direkt 123456789 und 123456787
haben den ggT 1 (
969=1·627+342
627=1·342+285
342=1·285+57
285=5·57+0 $ [mm] \Rightarrow [/mm] $ ggT ist also 57.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:46 Mi 28.02.2007 | | Autor: | oldpigweed |
Hallo leduart,
dank Dir für Deine Bemühung. Werde mal ne Aufgabe rechnen und hoffe es entstehen keine Fragen :o).
Mark
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:18 Mi 28.02.2007 | | Autor: | heyks |
Hallo Marc,
Du kannst dich schnell von davon überzeugen , daß dieser Algoritmus einen gemeinsamen Teiler von zwei natürlichen Zahlen liefert, denn durch
"Rückwärtseinsetzen" siehst Du, das a und b als Vielfaches des letzen Restes der Divison (in Deinem Beispiel also 57 ) dargestellt werden können.
Der Nachweis , dass dieser Rest wirklich der ggT von a und b liegt daran, dass jeder gemeinsame Teiler von a und b den ggT teilt .
LG
Heiko
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:24 Mi 28.02.2007 | | Autor: | oldpigweed |
Hallo Heiko,
danke für diese Erklärung.
Mark
|
|
|
|
