Woche 4 – Primfaktorzerlegung, Euler-Phi und Euklidischer Algorithmus

GGT

1. Berechne mittels euklidischem Algorithmus den ggT der folgenden Paare:
   1. (42, 6)
   2. (13, 4)
2. Berechne nun eine Darstellung des ggTs in der Form $ra + sb$, wobei $a,b$ jeweils ein Paar aus Aufgabe 1 ist.
3. Berechne für jede Zahl aus Aufgabenteil eins die zugehörige Primfaktorzerlegung.
4. Wie kann die Primfaktorzerlegung helfen, den ggT zu berechnen?

Euler-Phi

1. Angenommen ich habe eine Zahl $n$, was sagt mir die Zahl $\varphi(n)$?

2. Berechne folgende Werte: $\varphi(13), \varphi(8), \varphi(15)$

3. Wie kann die Primfaktorzerlegung helfen, den Wert $\varphi(n)$ zu berechnen?

   Tipp: Vielleicht helfen die Eigenschaften der Euler-Phi Funktion.