Erweiterter euklidischer Algorithmus

Aufrufe: 85     Aktiv: 28.08.2022 um 11:56

-2

Erläutern Sie wie man mit Hilfe des Erweiterten Euklidischen Algorithmus das

multiplikativ inverse Element mod n finden kann. Zeigen Sie dazu insbesondere

den mathematischen Zusammenhang, der dies erlaubt

Diese Frage melden
gefragt

Student, Punkte: -25

 
Kommentar schreiben
1 Antwort
1
Willst du Inverse von \(a\) in \(\mathbb{Z}/(n)\) finden müssen \(a\) und \(n\) teilerfremd sein. Mit euklidische Algorithmus in \(\mathbb{Z}\) finden wir \(x,y \in \mathbb{Z}\), so dass \(1=xa+yn\). Jetzt wende mal die kanonische Projektion \(\pi: \mathbb{Z}\to \mathbb{Z}/(n)\) bei beiden Seiten an. Denke daran das \(\pi\) ein Ringhomomorphismus ist.
Diese Antwort melden
geantwortet

Student, Punkte: 9.54K

 

Kommentar schreiben