GgT finden mit dem Algorithmus des Euklid |
30.01.2019, 20:47 | schildval | Auf diesen Beitrag antworten » | ||
GgT finden mit dem Algorithmus des Euklid Hallo, einige können es bestimmt nicht mehr sehen, aber hier ist noch eine Frage zum Algorithmus des Euklid (falls jemand die Lösung weiß oder weiß, wo sie steht, wird Löschung beantragt). Es heißt ja für ggT(a,b): oder allgemein . Woher weiß ich, dass der Teiler von a&b auch der gleiche Teiler von r1&b ist? Teilen mit Rest ist kein einfaches Multiplizieren oder Dividieren. Mit der allgemeinen Gleichung finde ich nur, dass es einen Teiler auf beiden Seiten gibt. Aber das könnte ja immer ein anderer sein, oder immer zwei verschiedene abwechselnd. Meine Ideen: Ist der gemeinsame Teiler in der Division mit Rest definiert? Wenn ja, dann kenne ich diese Definition nicht und wäre dankbar für Hinweise. |
||||
30.01.2019, 20:54 | HAL 9000 | Auf diesen Beitrag antworten » | ||
"Der Teiler" ??? Womöglich meinst du: Warum gilt ? An sich eine Grundeigenschaft des ggT, dieses für alle ganzen Zahlen , aber richtig, irgendwann mal sollte man diesen elementaren Beweis mal führen... |
||||
30.01.2019, 21:23 | schildval | Auf diesen Beitrag antworten » | ||
RE: GgT finden mit dem Algorithmus des Euklid Na ja "Teiler", weil ich davor noch gar nicht weiß, ob der ggT(r1,b) auch der gesuchte Wert ist, und das ganze kommt mir eh etwas rekursiv vor, auch wenn es das nicht ist. Aber o.k. das macht wieder einmal sehr schön sehr simpel sehr viel Sinn in dieser Hinsicht! *Thema-Wegräum-Zauber* |
||||
31.01.2019, 09:45 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Gut, hier der Beweis von : 1) Jeder gemeinsame Teiler von und ist auch ein Teiler von , damit ist er auch ein gemeinsamer Teiler von und . 2) Jeder gemeinsame Teiler von und ist auch ein Teiler von , damit ist er auch ein gemeinsamer Teiler von und . Zwei Paare mit derselben Menge gemeinsamer Teiler besitzen definitionsgemäß dann auch denselben größten gemeinsamen Teiler. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|