GgT finden mit dem Algorithmus des Euklid

30.01.2019, 20:47

schildval

GgT finden mit dem Algorithmus des Euklid

Meine Frage:
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): $\begin{eqnarray*} a = b*q_{1} + r_{1} \end{eqnarray*}$ oder allgemein $\begin{eqnarray*} r_{i-1} = r_{i}*q_{i+1} + r_{i+1} \end{eqnarray*}$ .

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 »

Zitat:

Original von schildval
Woher weiß ich, dass der Teiler von a&b auch der gleiche Teiler von r1&b ist?

"Der Teiler" ??? Womöglich meinst du: Warum gilt $\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(r_1,b) \end{eqnarray*}$ ?

An sich eine Grundeigenschaft des ggT, dieses $\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a-kb,b) \end{eqnarray*}$ für alle ganzen Zahlen $\begin{eqnarray*} a,b,k \end{eqnarray*}$ , 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!

Gott

*Thema-Wegräum-Zauber*

31.01.2019, 09:45

HAL 9000

Auf diesen Beitrag antworten »

Gut, hier der Beweis von $\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a-kb,b) \end{eqnarray*}$ :

1) Jeder gemeinsame Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ ist auch ein Teiler von $\begin{eqnarray*} a-kb = t\left(\frac{a}{t}+k\frac{b}{t}\right) \end{eqnarray*}$ , damit ist er auch ein gemeinsamer Teiler von $\begin{eqnarray*} a-kb \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ .

2) Jeder gemeinsame Teiler von $\begin{eqnarray*} a-kb \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ ist auch ein Teiler von $\begin{eqnarray*} (a-kb)+kb=a \end{eqnarray*}$ , damit ist er auch ein gemeinsamer Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ .

Zwei Paare mit derselben Menge gemeinsamer Teiler besitzen definitionsgemäß dann auch denselben größten gemeinsamen Teiler.

Neue Frage »

Antworten »

GgT finden mit dem Algorithmus des Euklid

Verwandte Themen