Euklidischer Algorithmus ggt(6n+13,3n+5)

Question

Hallo, wir befinden uns gerade in der Klausurvorbereitung und haben folgendes Problem: Wir müssen mithilfe des euklidischen Algorithmus zeigen, dass der ggt von 6n+13 und 3n+5 1 ist.

Aufgabe:

ggt(6n+13,3n+5)

Problem/Ansatz:

Wir haben bis jetzt:

6n+13= 2*(3n+5)+3

3n+5= 1*3+(3n+2)

3 = 0*(3n+2)+3

und ab hier hängt es.

Answer 1

Aloha :)

$$\operatorname{ggT}(6n+13,3n+5)=\operatorname{ggT}((6n+13)-(3n+5),3n+5)$$$$=\operatorname{ggT}(3n+8,3n+5)=\operatorname{ggT}((3n+8)-(3n+5),3n+5)$$$$=\operatorname{ggT}(3,3n+5)=\operatorname{ggT}(3,(3n+5)\operatorname{mod}3)=\operatorname{ggT}(3,2)$$$$=\operatorname{ggT}(3-2,2)=\operatorname{ggT}(1,2)=\operatorname{ggT}(1,2-1)=\operatorname{ggT}(1,1)=1$$

Answer 2

ggt(6·n + 13, 3·n + 5)

(6·n + 13) : (3·n + 5) = 2 Rest 3
(3·n + 5) : 3 = n Rest 5
5 : 3 = 1 Rest 2
3 : 2 = 1 Rest 1
2 : 1 = 2 Rest 0

Der ggt ist daher 1.

Answer 3

Hallo,

schreib Dir das am besten in Tabellenform, damit man nicht den Überblick verliert:

$$ \begin{array}{rr|rr} a& b&\lfloor a/b\rfloor & a - \lfloor a/b\rfloor\cdot b \\ \hline 6n+13 & 3n+5 & 2& 3 \\ 3n+5& 3& n+1& 2 \\ 3& 2& 1& 1 \\ 2& \colorbox{#ffff00}{1} & 2 & \checkmark \end{array} $$

sobald in der rechten Spalte eine 0 auftaucht (alias \(\checkmark\)), steht in der Spalte \(b\) der größte gemeinsame Teiler.