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.