0 Daumen
639 Aufrufe

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, •109)

Avatar von

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

das in sollte ein und* sein sorry

1 Antwort

0 Daumen

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

Avatar von 108 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community