0 Daumen
658 Aufrufe

Aufgabe: ggt (234,13)

mit dem euklidischen Algorithmus lösen!


Problem/Ansatz:

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

Avatar von

4 Antworten

+1 Daumen
 
Beste Antwort

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

Avatar von 48 k
0 Daumen
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.

Avatar von 53 k 🚀
0 Daumen

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.

Avatar von 148 k 🚀
0 Daumen

Der Euklidische Algorithmus geht so:

234 -13=219

219-13=206

206-13=193

193-13=...

....

13-13=0

Der ggT ist 13.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community