Euklidischer Algorithmus / ggT

30.08.2013, 23:54

baba2k

Euklidischer Algorithmus / ggT

Hallo zusammen,

wenn ich den ggT zweier Zahlen mit dem euklidischem Algorithmus berechnen will und die größere Zahl vorne steht, kann ich sie dann einfach vertauschen?

Also:

$\begin{eqnarray*} ggT(a,b)=ggT(b,a) \end{eqnarray*}$ ?

Beispiel:
Aufgabe: Berechnen Sie den größten gemeinsamen Teiler g = ggT(31,101).

$\begin{eqnarray*} ggT(31,101)=ggT(101,31) \end{eqnarray*}$

$\begin{eqnarray*} 101/3=3~Rest~8<br /> 31/8=3~Rest~7<br /> 8/7=1~Rest~1 \end{eqnarray*}$

$\begin{eqnarray*} ggT(31,101)=ggT(101,31)=ggT(31,8)=ggT(8,7)=ggT(7,1)=1 \end{eqnarray*}$

Vielen Dank!

Gruß baba

31.08.2013, 00:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von baba2k
Also:

$\begin{eqnarray*} ggT(a,b)=ggT(b,a) \end{eqnarray*}$ ?

Ist richtig. Freude