Satz von Euler in multiplikatives Inverse

Question

könnte mir jemand von euch sagen wie diese Aufgabe genau geht bzw. wie man da vorgeht bei so einer Art von Aufgaben:

a) Berechnen Sie die Eulersche phi-Funktion für n = 104

b) Berechnen Sie mit Hilfe des erweiterten euklidischen Algorithmus sowohl ggT(15, 109) als auch das Inverse von e = 15 in der multiplikativen Gruppe (Z*₁₀₉, •109)

Comments

.................................................

---

das in sollte ein und* sein sorry

Answer 1

Hallo

 du suchst die Anzahl  der zahlen mit ggT 1 mit 104  kannst aber zerlegen 104=8*13  φ(104)=φ(8)*φ(13) und die kannst du na den fingern abzählen für 8 und 13 ist prim und φ(p)=p-1,

der euklidische Algorithmus gibt dir die Darstellung des ggT hier 1 als 1=n*15+m*104 n,m aus Z

 dann ist n Inverse zu 15

wer allerdings das große 1 mal 1 also bis 20 kennt weiß 7*15=105

Gruß lul