Euklidischer Algorithmus

Neue Frage »

03.06.2018, 12:43	FelNa1109	Auf diesen Beitrag antworten »
Euklidischer Algorithmus Hi, ich bräuchte Hilfe bei der folgenden Aufgabe: (a) Zeigen Sie, mit dem Euklidischen Algorithmus, dass für zwei Zahlen $\begin{eqnarray} a,b\in \mathbb Z \end{eqnarray}$ gilt: $\begin{eqnarray} \exists x,y\in \mathbb Z : ggT(a,b) = xa + yb \end{eqnarray}$ (b) Folgern Sie daraus $\begin{eqnarray} (\mathbb Z / m\mathbb Z)^ = \left\{ [a] : 0<a<m, ggT(a,m)=1 \right\} \end{eqnarray}$ (c)* Listen Sie in beiden Fällen $\begin{eqnarray} m=15 \end{eqnarray}$ und $\begin{eqnarray} m=28 \end{eqnarray}$ jeweils die Elemente von $\begin{eqnarray} (\mathbb Z / m\mathbb Z)^ \end{eqnarray}$ und ihre Inversen auf (am besten in Tabellen mit dem Inversen der Elemente unter den Elementen). Meine Ideen:* Ich hab mich bis jetzt an der a) versucht. Da das aber relativ viel ist, werd ichs mal ins erste Kommentar verfrachten, damit das Thema (also die Aufgabenstellung) übersichtlich bleibt. Von daher bitte noch etwas Geduld und Danke für die Hilfe.
03.06.2018, 12:57	Elvis	Auf diesen Beitrag antworten »
(a) Die Darstellung des ggT als Summe liefert der "erweiterte" euklidische Algorithmus ( https://de.wikipedia.org/wiki/Erweiterte...her_Algorithmus ), wobei mir die Matrizendarstellung besonders zusagt. (b) ist eine eine einfache Folgerung und (c) ein kleines Beispiel.
03.06.2018, 13:16	FelNa1109	Auf diesen Beitrag antworten »
zur (a): Zu zeigen: $\begin{eqnarray} \exists x,x \im \mathbb Z : ggT(a,b) = xa + yb \end{eqnarray}$ für $\begin{eqnarray} a,b \in \mathbb Z \end{eqnarray}$ mit Euklidischen Algorithmus. Nach Satz 3.37 (der Algorithmus in meiner VL) erzeugt der Euklidische Algorithmus eine Folge von Resten $\begin{eqnarray} (d_i)_{i\in \mathbb N} \end{eqnarray}$ definiert durch: $\begin{eqnarray} d_0 = a \end{eqnarray}$ $\begin{eqnarray} d_1 = b \end{eqnarray}$ $\begin{eqnarray} d_{i+1} = \end{eqnarray}$ Rest der Division von $\begin{eqnarray} d_{i-1} \end{eqnarray}$ durch $\begin{eqnarray} d_i \end{eqnarray}$ falls $\begin{eqnarray} d_i\neq 0 \end{eqnarray}$ , sonst Null. ...sowie eine Folge von Quotienten $\begin{eqnarray} (q_i)_{i\in \mathbb N} \end{eqnarray}$ , sodass wir in jedem Schritt folgende Darstellung erhalten: $\begin{eqnarray} d_{i-1} = q_id_i + d_{i+1}, \| d_{i+1} \| < \| d_i \| \end{eqnarray}$ Man betrachte nun die Restklassen mod b. Offensichtlich gilt $\begin{eqnarray} d_0 = a = 1a + 0b \end{eqnarray}$ sowie $\begin{eqnarray} d_1 = b = 0a + 1b \end{eqnarray}$ $\begin{eqnarray} \Rightarrow d_0, d_1 \end{eqnarray}$ sind Vielfache von $\begin{eqnarray} a \end{eqnarray}$ , nach Hinzufügen/Abziehen von Vielfachen von $\begin{eqnarray} b \end{eqnarray}$ . $\begin{eqnarray} \Rightarrow \end{eqnarray}$ die Restklassen $\begin{eqnarray} \left[d_i\right]_b \end{eqnarray}$ sind Vielfache der Restklassen $\begin{eqnarray} \left[a\right]_b \end{eqnarray}$ für $\begin{eqnarray} k=0,1,2,... \end{eqnarray}$ Wir konstruieren nun eine Folge $\begin{eqnarray} (s_i)_{i\in \mathbb N} \end{eqnarray}$ wie folgt: $\begin{eqnarray} s_0 = a \end{eqnarray}$ $\begin{eqnarray} s_1 = 0 \end{eqnarray}$ $\begin{eqnarray} d_i \equiv s_i a (mod b) \end{eqnarray}$ $\begin{eqnarray} s_{i-1} \equiv q_is_i + s{i+1} \end{eqnarray}$ Führt man nun den euklidischen Algorithmus aus, mit $\begin{eqnarray} d_{i+1} = d_{i-1} - q_id_i \end{eqnarray}$ und $\begin{eqnarray} s_{i+1} = s_{i-1} - q_is_i \end{eqnarray}$ ist nach endlich vielen Schritten $\begin{eqnarray} d_{i+1} = 0 \end{eqnarray}$ also für $\begin{eqnarray} n \end{eqnarray}$ : $\begin{eqnarray} d_n = ggT(a,b) \end{eqnarray}$ und $\begin{eqnarray} ggT(a,b) \equiv s_na (mod b) \end{eqnarray}$ . Wir erhalten so noch eine weitere Folge $\begin{eqnarray} (t_i)_{i\in \mathbb N} \end{eqnarray}$ mit $\begin{eqnarray} t_i := (d_i - s_ia) = k_ib + 0 \Rightarrow t_i = (d_i -s_ia)/b = k_i \end{eqnarray}$ Diese Folge ist gegeben durch $\begin{eqnarray} t_0 = 0 \end{eqnarray}$ $\begin{eqnarray} t_1 = 1 \end{eqnarray}$ $\begin{eqnarray} t_{i-1} \equiv q_id_i + t_{i+1} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Wir erhalten im letzten ( $\begin{eqnarray} n- \end{eqnarray}$ ten) Schritt: $\begin{eqnarray} ggT(a,b) = d_n = s_na + (d_n - s_na)/b b = s_na + t_nb \end{eqnarray}$ Aussage folgt für $\begin{eqnarray} s_n := x \end{eqnarray}$ und $\begin{eqnarray} t_n := y \end{eqnarray*}$ .
03.06.2018, 14:12	Elvis	Auf diesen Beitrag antworten »
Ja, das ist die klassische Darstellung. Matrizen gefallen mir besser, weil damit alles sehr durchsichtig auf ein Matrizenprodukt zurückgeführt wird und nicht mit endlichen Folgen von Zahlen operiert wird.
03.06.2018, 14:18	FelNa1109	Auf diesen Beitrag antworten »
Also weiter im Text! Zur (b) hätte ich jetzt glaube ich die eine Richtung, aber bei der anderen haperts leider noch. zur (b): " $\begin{eqnarray} \supseteq \end{eqnarray}$ " Sei $\begin{eqnarray} A := \left\{ \left[a\right] : 0<a<m, ggT(a,m) = 1 \right\} \end{eqnarray}$ und $\begin{eqnarray} \left[a\right]\in A \end{eqnarray}$ . Nach der vorherigen Aufgabe $\begin{eqnarray} \exists x,y \in \mathbb Z : ggT(a,m) = 1 = ax + my \end{eqnarray}$ . $\begin{eqnarray} \Rightarrow 1 \equiv ax (mod m) \end{eqnarray}$ . Also $\begin{eqnarray} \left[a\right] \in \left(\mathbb Z / m \mathbb Z\right)^* \end{eqnarray*}$
03.06.2018, 15:36	FelNa1109	Auf diesen Beitrag antworten »
Und falls es interessiert (erwarte nicht das das irgendwer hier nachrechnet ) hab ich für c) folgendes gemacht: Vorgehensweise: 1. $\begin{eqnarray} ggT(a,m) \end{eqnarray}$ bestimmen für $\begin{eqnarray} 0<a<m \Rightarrow ggT(a,m) \neq 1 \end{eqnarray}$ , dann nach b) nicht invertierbar 2. ist $\begin{eqnarray} ggT(a,m)=1 \end{eqnarray}$ , dann nach a) $\begin{eqnarray} ggT(a,m) = ax + my \end{eqnarray}$ Also $\begin{eqnarray} 1 \equiv ax (mod m), x \end{eqnarray}$ muss bestimmt werden. $\begin{eqnarray} a\in \mathbb Z/ 15\mathbb Z \leftrightarrow a^{-1} \end{eqnarray}$ $\begin{eqnarray} 1 \leftrightarrow 1 \end{eqnarray}$ $\begin{eqnarray} 2 \leftrightarrow 8 \end{eqnarray}$ $\begin{eqnarray} 4 \leftrightarrow 4 \end{eqnarray}$ $\begin{eqnarray} 7 \leftrightarrow 13 \end{eqnarray}$ $\begin{eqnarray} 8 \leftrightarrow 2 \end{eqnarray}$ $\begin{eqnarray} 11 \leftrightarrow 11 \end{eqnarray}$ $\begin{eqnarray} 13\leftrightarrow 7 \end{eqnarray}$ $\begin{eqnarray} 14\leftrightarrow 14 \end{eqnarray*}$ Zweite Tabelle geht analog, bin aber zu faul zum Eintippen.
Anzeige

03.06.2018, 15:59	FelNa1109	Auf diesen Beitrag antworten »
Und hier noch die fehlende Richtung von (b): " $\begin{eqnarray} \subseteq \end{eqnarray}$ " Sei $\begin{eqnarray} [a] \in (\mathbb Z / m \mathbb Z)^ \Rightarrow \exists [b]\in (\mathbb Z / m \mathbb Z)^* \end{eqnarray}$ mit $\begin{eqnarray} 1 \equiv ab (mod m) \end{eqnarray}$ (nennen wir mal (x)) $\begin{eqnarray} \Rightarrow a\neq 0 , a\neq m \end{eqnarray}$ , da gilt: $\begin{eqnarray} 1 \neq 0 \equiv 0 (mod m) = m (mod m) \end{eqnarray}$ Einen Repräsentanten von $\begin{eqnarray} [b] \end{eqnarray}$ kann man mit dem Euklidischen Algorithmus angewendet auf $\begin{eqnarray} a,m \end{eqnarray}$ finden. Dann $\begin{eqnarray} \exists x,y \in \mathbb Z : ggT(a,m) = ax + my \end{eqnarray}$ nach Aufgabe a), also insbesondere $\begin{eqnarray} ax (mod m) \end{eqnarray}$ Ist nun $\begin{eqnarray} x \end{eqnarray}$ ein Repräsentant von $\begin{eqnarray} [b] \end{eqnarray}$ , so gilt wegen (x) auch $\begin{eqnarray} ggT(a,m) = 1 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow [a] \in A \end{eqnarray*}$
03.06.2018, 18:12	Elvis	Auf diesen Beitrag antworten »
c) habe ich selbstverständlich überprüft und für gut befunden. b) die fehlende Richtung fehlt noch immer ... (ich habe einen elementaren Beweis)
03.06.2018, 18:35	FelNa1109	Auf diesen Beitrag antworten »
Danke das du über die c) geschaut hast, weiß ich zu schätzen! Deinem Wortlaut nehm ich mal an das die andere Richtung von der b) passt, also zu der letzten: Da bin ich ehrlich gesagt, stark am überlegen... Die $\begin{eqnarray} (\mathbb Z / m\mathbb Z )^ \end{eqnarray}$ enthält doch gerade die invertierbaren Restklassen von $\begin{eqnarray} \mathbb Z / m\mathbb Z \end{eqnarray}$ . Also z.B. $\begin{eqnarray} a + m\mathbb Z \end{eqnarray}$ , aber sind dann nicht notwendigerweise $\begin{eqnarray} a \end{eqnarray}$ und $\begin{eqnarray} m \end{eqnarray}$ immer teilerfremd? Also $\begin{eqnarray} a\neq m, a\neq 0 \end{eqnarray}$ und damit auch $\begin{eqnarray} ggT(a,m)=1 \end{eqnarray*}$ ?
03.06.2018, 18:46	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} a\ne 0 \end{eqnarray}$ ist schon mal richtig, $\begin{eqnarray} 1\equiv ax \mod m \end{eqnarray}$ stimmt auch ... aber wie folgt daraus $\begin{eqnarray} ggT(a,m)=1 \end{eqnarray}$ ?
03.06.2018, 19:24	FelNa1109	Auf diesen Beitrag antworten »
Naja, für $\begin{eqnarray} x=1 \end{eqnarray}$ hätten wir ja $\begin{eqnarray} 1 \equiv a (mod m) \end{eqnarray}$ . Das heißt ja, das die sich nur um ganzzahlige Vielfache unterscheiden, also $\begin{eqnarray} a = km + 1 \end{eqnarray}$ mit $\begin{eqnarray} k\in \mathbb Z \end{eqnarray}$ darauf kann man ja den Euklidischen Alg werfen mit $\begin{eqnarray} d_0 = a, d_1 = m \end{eqnarray}$ und hat dann: 0.Schritt:* $\begin{eqnarray} d_0 = q_1d_1 + d_2 \end{eqnarray}$ also $\begin{eqnarray} a = q_1m + 1 \end{eqnarray}$ 1.Schritt: $\begin{eqnarray} m = 1m + 0 \end{eqnarray}$ $\begin{eqnarray} d_{min\left\{ k : d_{k+1} = 0\right\} } = d_2 = 1 \end{eqnarray}$ also $\begin{eqnarray} ggT(a,m) = 1 \end{eqnarray*}$
03.06.2018, 19:35	Elvis	Auf diesen Beitrag antworten »
Das ist nicht hinreichend. Damit hast du nur den trivialen Fall a=1 erwischt. Wenn du weiter arbeiten möchtest, darfst du das gerne tun. Bevor du verzweifelt aus dem Kellerfenster springst, darfst du mich auch um meinen elementaren Beweis bitten ... bis 20:00 bin ich online ...
03.06.2018, 19:45	FelNa1109	Auf diesen Beitrag antworten »
Ok, dann bitte ich einmal höflich um einen elementaren Beweis. Dankeschön
03.06.2018, 19:48	Elvis	Auf diesen Beitrag antworten »
Dem Antrag wird stattgegeben: Einerseits $\begin{eqnarray} a\in (\mathbb Z/m\mathbb Z)^\Rightarrow 1\equiv ax\mod m\Rightarrow m\|(1-ax)\Rightarrow my=1-ax\Rightarrow 1=ax+my \end{eqnarray}$ Andererseits $\begin{eqnarray} d:=ggT(a,m)=ax'+my'\Rightarrow d=d\cdot 1=d(ax+my)=adx+mdy=d^2(\frac a d x+\frac m d y)\Rightarrow d^2\|d\Rightarrow d=\pm 1\Rightarrow ggT(a,m)=1 \end{eqnarray*}$

Neue Frage »

Antworten »

Euklidischer Algorithmus

Verwandte Themen