Beweis zum ggT

22.03.2014, 14:10	Vazrael	Auf diesen Beitrag antworten »
Beweis zum ggT Hi, Ich möchte zeigen $\begin{eqnarray} ggT(a_1, a_2, ..., a_s) = ggT(a_1, r_2, ..., r_s) \end{eqnarray}$ wenn $\begin{eqnarray} a_1 < a_2, a_3, ..., a_s \end{eqnarray}$ und $\begin{eqnarray} r_i \end{eqnarray}$ den Rest bezeichnet, den man bei Division von $\begin{eqnarray} a_i \end{eqnarray}$ durch $\begin{eqnarray} a_1 \end{eqnarray}$ erhält. Beweis über vollständige Induktion: Sei n=2: Zu zeigen ist $\begin{eqnarray} ggT(a_1, a_2) = ggT(a_1, r_2) \end{eqnarray}$ . Zunächst gilt $\begin{eqnarray} ggT(a_1, a_2) = ggT(a_1, a_2 - a_1) \end{eqnarray}$ , da ja laut Annahme $\begin{eqnarray} a_1 < a_2 \end{eqnarray}$ . Da es einen Rest gibt, ergibt es die folgende Darstellung $\begin{eqnarray} a_2 = q \cdot a_1 + r_2 \end{eqnarray}$ . Damit ist aber auch $\begin{eqnarray} a_2 - (q-1)\cdot a_1 > a_1 \end{eqnarray}$ und man erhält schließlich $\begin{eqnarray} ggT(a_1, a_2) = ggT(a_1, a_2 - a_1) = ... = ggT(a_1, a_2 - q\cdot a_1) = ggT(a_1, r_2) \end{eqnarray}$ . Sei die Behauptung also für n bereits gezeigt. Zu zeigen ist die Behauptung nun für n+1. Es gilt dabei $\begin{eqnarray} ggT (a_1, ..., a_n, a_{n+1}) = ggT( ggT(a_1, ..., a_n), a_{n+1}) = ggT(ggT(a_1, r_2, ..., r_n), a_n+1) = \end{eqnarray}$ ? Wie gehts weiter?
22.03.2014, 19:47	ollie3	Auf diesen Beitrag antworten »
RE: Beweis zum ggT hallo, weiter geht es so: $\begin{eqnarray} ...=ggT(a_1, r_2,...,r_n,a_{n+1}-qa_1)<br /> =ggT(a_1, r_2,...r_n, r_{n+1}) \end{eqnarray*}$ , wobei man q so wählt, das man wieder einen rest r_{n+1} erhält, der kleiner als a_1 ist. gruss ollie3

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »