Größter gemeinsame Teiler mit dem euklidischen Algorithmus: ggt (234,13)

Question

Aufgabe: ggt (234,13)

mit dem euklidischen Algorithmus lösen!

Problem/Ansatz:

Laut Lösung kommt 13 heraus, aber wie kommt man darauf?

Answer 1

Hallo Furkan,

der größte gemeinsame Teiler ist ein Teiler, das heißt eine Zahl die sowohl 234 als auch 13 teilt. Nun ist 13 aber ohne Zweifel eine Primzahl, die nur die Teiler 1 und 13 hat. Und da $234 = 13 \cdot 18$ ist, ist $13$ der größte gemeinsame Teiler. Aber nicht 18 (18 ist größer als 13, das geht gar nicht) oder 5. Wenn eine Zahl durch 5 teilbar wäre, so wäre die letzte Ziffer eine 0 oder eine 5. Das ist bei beiden Zahlen nicht der Fall.

Der Euklidische Algorithmus wäre in diesem Fall:$$\begin{array}{rr|r} r& s& \lfloor r/s \rfloor\\ \hline 234& 13& 18 \\ 13& 0& - \end{array}$$.. und damit ist es schon erledigt. Der $\text{ggt}(234,\,13)=13$

Gruß Werner

Answer 2

laut der Lösung ist es die 5

Das ist völliger Unfug. 234 ist nicht durch 5 teilbar, und 13 ist auch nicht durch 5 teilbar.

Also kann 5 kein gemeinsamer Teiler von 234 und 13 sein.

Die 13 hat als Primzahl nur zwei Teiler: 1 und 13. Du kannst also nur probieren, ob 13 eventuell auch ein Teiler von 234 ist.

Answer 3

Aloha :)

13 ist weder durch 5 noch durch 18 teilbar, also sind beide genannten Ergebnisse falsch. Richtig ist:

$$\text{ggT}(234,13)=\text{ggT}(234\; \text{mod}\; 13,13)=\text{ggT}(0,13)=13$$

Da $234/13=18$ ohne Rest teilbar ist, ist 234 mod 13=0 und der Euklidische Algorithmus endet sehr schnell.

Answer 4

Der Euklidische Algorithmus geht so:

234 -13=219

219-13=206

206-13=193

193-13=...

....

13-13=0

Der ggT ist 13.