scattered-lenity

| Definition (5.3) | (erweiterter) euklidischer Algorithmus |

anchored to [[104.00_anchor_math]] proceeds from [[104.11_elementare_zahlentheorie]] also possible in [[104.14_PolynomRinge]]

| Overview |

Wir können den euklidischen Algorithmus verwenden, um von zwei gegebenen Zahlen den [[104.11_elementare_zahlentheorie#Definition (5.1) ggT/gcd - größter gemeinsamer Teiler|ggt]] zu berechnen!

Unter Anwendung des erweiterten euklidischen Algorithmus wird es uns weiterhin ermöglicht den ggT in einer neuen Schreibweise $\gcd (a,b)=s\cdot a+t\cdot b$ darzustellen, die wir in manchen Bereichen anwenden können.

| Definition |

[!Definition] Beschreibung | Ablauf des euklidischen Algorithmus: Wir erhalten als Eingabe folgend; $a,b\in \mathbb{Z}$ hierbei dürfen beide nicht $0$ sein. Wir möchten ihn jetzt mit PseudoCode beschreiben:

if $b=0$ then $y:=\mid a\mid$ endif if $b\mid 0$ then $y:=\mid b\mid$ endif if $b\ne 0\wedge b\ne a$ then: $x:=a,y:=b$, enter loop: while now $x\mathrm{mod}y\ne 0$ do: $r:=x\mathrm{mod}y$ $x:=y$ $y:=r$ endwhile endif

Wir erhalten damit dann den ggT folgend: $$\begin{gathered} y(= \\ gcd(a,b)) \end{gathered}$$

[!Important] die größere Zahl sollte immer vorn stehen! Denn dadurch sparen wir uns einen Schritt, welchen wir sonst durchführen müssten. ( siehe slides #TODO )

[!Important] Möglichkeit: nur mit Betrag rechnen Wir können den ggT mit dem obig definierten euklidischen Algorithmus auch nur mit dem Betrag der beiden Zahlen berechne. Das heißt wir brauchen hierbei dann nicht mit negativen Werten rechnen. Dafür müssen wir dann jedoch beim [[#Definition erweiterter eukl. Algorithmus]] aufpassen

| Beispiel für euklidischer Algorithmus |

Wir möchten jetzt ein Beispiel des Algorithmus durchlaufen. Damit sollte das Prinzip der Berechnung ersichtlicher werden

[!Attention] Variante des Aufschreibens Es gibt viele verschiedene Arten diesen Algorithmus und seine Schritte aufzuschreiben. Wir werden hier beispielhaft die Form einer Tabelle betrachten

Sei jetzt $a=48,b=-39$ wir möchten den ggT beider finden:

Haben wir diese Tabelle, müssen wir jetzt den letzten Wert vor dem Rest $=0$ betrachten und dieser wird dann unser ggT sein!

Also folgend: $gcd(48,-30)=6$

| Satz (5.5) | Lemma von Bachet de Mézirac | lange Schreibweise eines ggT

Seien jetzt wieder $a,b\in \mathbb{Z}$, wobei beide $\ne 0$ $$\begin{gathered} ⟹\exists s,t\in \mathbb{Z}: \\ gcd(a,b)=s\cdot a+t\cdot b \end{gathered}$$ Wir können also den ggT von zwei Zahlen auch folgend aufschreiben und somit etwas ausführlicher darstellen!

[!Important] Intuition Wir sehen hier, dass beide Werte irgendwie multipliziert werden können, sodass sie dann den gleichen Wert repräsentieren. Unter Anwendung des euklidischen Algorithmus können wir entsprechend diese beiden Werte berechnen, sodass wir diese Darstellung dann übernehmen können.

| Beweis des Lemma |

Wir betrachten jetzt folgend und möchten es via Induktion beweisen:

Sei folgend: $$\begin{array}{rl}b=0& \gcd (s,b)=\mid a\mid =s\cdot a+0\cdot b,s=\{\begin{array}{ll}1& \text{ falls }a>0\\ -1& \text{ falls }a<0\end{array}\\ b\ne 0,b\mid a& :\gcd (a,b)=\mid b\mid =0\cdot a+t\cdot b,t=\{\begin{array}{ll}1& \text{ falls}b>0\\ -1& \text{ falls}b>0\end{array}\\ & \\ b\ne 0,b\nmid a:& \text{ setze jetzt }{a}_0=a,a_1=b\text{ und wende eukl Algo an}:\\ a_0=& q_1\cdot a_1+a_2\\ a_1=& q_2\cdot a_2+a_3\\ \dots & \\ a_{n-1}=& q_n\cdot a_n+0\\ ⟹a_n=\gcd (a_0,,a_1),(n\ge 2)& \end{array}$$ Das zeigen wir jetzt nocht mit der Induktion über j: $\exists s_j,t_j\in \mathbb{Z}:a_j=s_j\cdot a_0+t_j\cdot a_1$ mit $j=0,\dots n$ und weiterhin ist auch noch $a_0=a,a_1=b$

$$\begin{aligned} \text{ IA}: & & \ j = 0 & a_{0} = s_{0} \cdot a_{0} + t_{0} \cdot a_{1}, s_{0} = 1, t_{0}=0~\square\ j = 1 & a_{1} = s_{1} \cdot a_{0} + t_{1} \cdot a_{1}, s_{1} = 0, t_{1} = 1~\square\ \text{IS}: j-1, j- 2 \implies j & & \ \text{ Sei} $j \geq 2$ \text{ und es gelte jetzt:} && \ a_{j-2} = &s_{j-2} \cdot a_{0} + t_{j-2} \cdot a_{1} \ a_{j-1} = & s_{j-1} \cdot a_{0} + t_{j-1} \cdot a_{1} \ \text{Dann folgt jetzt (IV!)}: &&\ a_{j} = a_{j-2} - q_{j-1} \cdot (a_{j-1}) \ =& s_{j-2} \cdot a_{0} + t_{j-2} \cdot a_{1} ~ - q_{j-1} \cdot s_{j-1} \cdot a_{0} + t_{j-1} \cdot a_{1} \ = & (s_{j-2} - q_{j-1} \cdot s_{j-1} ) \cdot a_{0} + ( t_{j-2} - q_{j-1} \cdot) \end{aligned}$$

| Definition | erweiterter eukl. Algorithmus

Folglich ist der erweiterte euklidische Algorithmus als PseudoCode angegeben, weil er sehr ausführlich in seiner Ausführung ist: ![[Pasted image 20231204131756.png]]

| alternative Schreibweise für erw. eukl. Algorithmus |

Wir haben das vorherige [[#Beispiel für euklidischer Algorithmus]] nochmals unter Anwendung des erweiterten Euklidhschen Algorithmus betrachtet.

[!Tip] Jameels Schreibweise Jameel hat eine alternative Schreibweise zum berechnen und niederschreiben des erw. eukl. Algo gezeigt, mit welcher es schneller und schöner möglich ist, alles zu berechnen:

Selbiges Beispiel, wie vorher:

[!Task] Bestimmen von $\gcd (48,-30)$ wir möchten auch hier nochmal den ggT von $a=48,b=-30$ bestimmen, aber dies mal in der Schreibweise von $s\cdot a+tcdotb$

[!Important] Intuition Prinzipielle möchte man also durch rückwärtseinsetzen die beiden Werte $s,t$ bestimmen. Dazu schreiben wir jetzt folgend jeden Schritt des eukl ALgorithmus mit der Divions mit Rest auf. und am Ende möchten wir diese erhaltenen Kombinationen wieder einsetzen, bis man dann den $\gcd (a,b)$ erhält.

Wir schreiben folgend: $$\begin{array}{rlr}48=& -1(-30)+18& \\ -30=& -2\cdot 18+6& (-30\text{als lk von }18!)\\ 18=& 3\cdot 6+0& (18\text{ wieder als LK von }6)\\ \text{ Betrachte jetzt die Zeile vor dem Rest 0!}:& & \\ & 6=-30+2\cdot 18& \text{ wie schreiben wir 18 auf?, betrachte Zeile davor!}\\ & -30+2\cdot (48+(-30))& \\ & 2\cdot 48+3(-30)& \text{ wir haben den vorherigen Term zusammengefasst!}\end{array}$$ Wir haben die 48 umgeschrieben, jetzt haben wir den GGT mit 6 gefunden und möchten diesen jetzt so umschreiben, dass er als Kombination der beiden Ausgangswerte gebildet werden kann!

Dafür nehmen wir die Gleichung, wo der GGT auftritt und schreiben ihn so um ,dass $6$ das Ergebnis ist. Danach müssen wir jetzt die vorherigen Gleichungen nochmal anschauen ( wir müssen ja die ursprünglichen Werte nochmal anwenden).

| Anwendung des erw. eukl. Algorithmus |

Angewandt werden kann dieser Algorithmus, um etwa das multiplikative Inverse eines Wertes $z\in {\mathbb{Z}}_m$, wobei (${\mathbb{Z}}_m\odot$), bestimmen zu können.

In dieser Struktur hattten wir gezeigt, dass: $z\in {\mathbb{Z}}_m$ invertierbar $⟺\gcd (z,m)=1$ !

[!Example] etwa in $Z_6⟹2\odot x=1$

In dieser Betrachtung liefer der erw. eukl. Algorithmus zu $z$ und $m$ dann die Zahlen $s,t\in \mathbb{Z}$, sodass gilt: $z\cdot s+m\cdot t=1=\gcd (z,m)$ $$\begin{array}{rl}⟹(z\cdot s)\mathrm{mod}(m)=1& =\\ z\odot s=1,\in {\mathbb{Z}}_m& \\ ⟹z^{-1}=s\mathrm{mod}(m)& \end{array}$$

Beispiel dazu:

$$\begin{array}{r}{3}^{-1}\in {\mathbb{Z}}_7?\\ erw.eukl.alg:3\cdot (-2)+7\cdot (1)=1=\gcd (3,7,)\\ ⟹-2\mathrm{mod}(7)=5⟹3^{-1}=5\in {\mathbb{Z}}_7\end{array}$$

ein weiteres Beispiel findet sich folgend: ![[104.87_assignment06#Aufgabe 3]]

Diese Umformung ist gerade bei Anwendung von [[104.11_elementare_zahlentheorie#Anwendung Zahlentheorie RSA]] wichtig, weil somit der private Schlüssel berechnet werden kann!