Wieso funktioniert der Euklidische Algorithmus?

Neue Frage »

02.10.2011, 16:40	Selin	Auf diesen Beitrag antworten »
Wieso funktioniert der Euklidische Algorithmus? Meine Frage: Wie der Euklidische Algorithmus zur ggT-Bestimmung funktioniert, ist mir eigentlich klar. Allerdings werden in unseren mündlichen Prüfungen häufig Fragen gestellt, warum seine Ausführung überhaupt richtig ist, also warum man ihn anwenden darf. Danke schon mal im Voraus für eure Überlegungen! Meine Ideen: -
02.10.2011, 16:45	Math1986	Auf diesen Beitrag antworten »
RE: Wieso funktioniert der Euklidische Algorithmus? Wenn dir klar ist wie er funktioniert, dann beschreib ihn noch mal. Dann sollte dir nämlich auch klar sein warum er funktioniert.
02.10.2011, 16:50	Selin	Auf diesen Beitrag antworten »
RE: Wieso funktioniert der Euklidische Algorithmus? Also, der euklidische Algorithmus ist zur Berechnung des ggT von 2 Zahlen, z.B. a und b. Es sind Division-mit-Rest-Aufgaben. Wenn a die größere Zahl ist, kann man wie folgt beginnen: a=Quotient1b+Rest1, wobei der Rest logischerweise kleiner ist als der Quotient. b=Quotient2Rest1+Rest2 ... Rest(n-3)=Quotient(n)*Rest(n-1)+0 --> ggT(a,b)=Rest(n-1) Warum das so ist, weiß ich nicht. Ich weiß nur, dass man es halt immer so rechnet
02.10.2011, 16:55	Leopold	Auf diesen Beitrag antworten »
Wenn $\begin{eqnarray} a \operatorname{mod} b \end{eqnarray}$ die Berechnung des Restes bei der Division von $\begin{eqnarray} a \end{eqnarray}$ durch $\begin{eqnarray} b \end{eqnarray}$ bedeutet ( $\begin{eqnarray} a,b \end{eqnarray}$ seien positive ganze Zahlen), so folgt alles aus der rekursiven Beziehung $\begin{eqnarray} \operatorname{ggT} \left( a,b \right) = \operatorname{ggT} \left( b,a \operatorname{mod} b \right) \end{eqnarray}$ Überlege dir, warum diese Beziehung gelten muß. Der Rest folgt durch ihre mehrfache Anwendung. Die Rekursion endet, wenn a $\begin{eqnarray} \operatorname{mod} b = 0 \end{eqnarray}$ ist. Dann ist $\begin{eqnarray} \operatorname{ggT}(a,b) = b \end{eqnarray}$ . Beispiel: $\begin{eqnarray} \operatorname{ggT}(525,140) = \operatorname{ggT}(140,105) = \operatorname{ggT}(105,35) = 35 \end{eqnarray}$
02.10.2011, 17:06	Selin	Auf diesen Beitrag antworten »
Ich weiß einfach nicht wie man darauf kommen soll, dass das gilt. Bei einem Beispiel (ggT von 15 und 5) , kommt man durch das Verfahren zwar auf das richtige Ergebnis, aber warum man das rechnen darf, ich mir noch nicht ganz klar...
02.10.2011, 17:12	Math1986	Auf diesen Beitrag antworten »
Was ist dir an der Rechnung von Leopold unklar?
Anzeige

02.10.2011, 17:17	Selin	Auf diesen Beitrag antworten »
Ich check einfach nicht warum diese Beziehung gelten muss...Vielleicht sollt ichs einfach aufgeben Sachen verstehen zu wollen...
02.10.2011, 17:19	Math1986	Auf diesen Beitrag antworten »
Es ist ja gut, die Sachen verstehen zu wollen, welche Sache meinst du nun genau?
02.10.2011, 17:21	Selin	Auf diesen Beitrag antworten »
Warum gilt ggT(a,b)=ggT(b,a mod b)? Also warum darf man das?
03.10.2011, 17:57	Leopold	Auf diesen Beitrag antworten »
Vielleicht versteht man es so besser: Besitzen die positiven ganzen Zahlen $\begin{eqnarray} a \end{eqnarray}$ und $\begin{eqnarray} b \end{eqnarray}$ (mit $\begin{eqnarray} a \geq b \end{eqnarray}$ ) einen gemeinsamen Teiler, so teilt dieser auch $\begin{eqnarray} a+b \end{eqnarray}$ und $\begin{eqnarray} a-b \end{eqnarray}$ . Insbesondere gilt das für den größten gemeinsamen Teiler. Man folgert: $\begin{eqnarray} \operatorname{ggT}(a,b) = \operatorname{ggT}(a-b,b) \end{eqnarray}$ Das führt man so lange fort, bis die Differenz schließlich kleiner als $\begin{eqnarray} b \end{eqnarray}$ ist. Und damit hat man die Division mit Rest. Bei meinem vorigen Beispiel wären also in $\begin{eqnarray} \operatorname{ggT}(525,140) = \operatorname{ggT}(140,105) \end{eqnarray}$ beim Gleichheitszeichen noch die folgenden Schritte einzuschieben: $\begin{eqnarray} \operatorname{ggT}(525,140) = \operatorname{ggT}(385,140) = \operatorname{ggT}(245,140) = \operatorname{ggT}(105,140) \end{eqnarray}$
04.10.2011, 16:41	Selin	Auf diesen Beitrag antworten »
danke!
05.10.2011, 16:59	Selin	Auf diesen Beitrag antworten »
ggT(a,b)=ggT(a-b,b) (a-b), weil in einer Gruppe die Abgeschlossenheit gilt und (a-b)=(a+(-b)) wäre?
09.10.2011, 10:14	Selin	Auf diesen Beitrag antworten »
Oder hat das eine andere Begründung?
09.10.2011, 14:30	Leopold	Auf diesen Beitrag antworten »
Also mit Gruppentheorie hat das nun gar nichts zu tun. Wir befinden uns hier ganz im Elementarbereich der positiven ganzen Zahlen. Stelle dir einen Baumstamm der Länge $\begin{eqnarray} a \end{eqnarray}$ und einen der Länge $\begin{eqnarray} b \end{eqnarray}$ vor. Jetzt zersägst du diese in lauter Stücke gleicher Länge $\begin{eqnarray} c \end{eqnarray}$ , so daß nicht ein Fitzelchen Rest übrigbleibt. Nehmen wir einmal an, daß $\begin{eqnarray} a \end{eqnarray}$ länger als $\begin{eqnarray} b \end{eqnarray}$ ist. Dann ist es doch augenscheinlich, daß man auch einen Baumstamm der Länge $\begin{eqnarray} a-b \end{eqnarray}$ in Stücke der Länge $\begin{eqnarray} c \end{eqnarray}$ ohne Rest zersägen kann (Bildchen malen). Beispiel: a=5,60 m; b=4,55 m; c=0,35 m Natürlich kann man das alles auch ganz formal mit der Definition der Teilbarkeit nachweisen.

Neue Frage »

Antworten »

Wieso funktioniert der Euklidische Algorithmus?

Verwandte Themen