Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Informatik in der Schule (http://www.informatikerboard.de/board/board.php?boardid=21)
--- Modulare Inverse ? (http://www.informatikerboard.de/board/thread.php?threadid=570)
Geschrieben von J.Dylan am 18.08.2009 um 01:19:
Modulare Inverse ?
Hallo,
Ich hätte da gleich noch ne Frage und hoffe ihr könnt mir helfen.
Wie berechne ich eine Modulare Inverse und verstehe ich das schon richtig eine modulare inverse zu einer Zahl ist lediglich die zahl a mit der ich eine Zahl b multiplizieren muss um beim Teilen durch eine Dritte Zahl m, 1 zu erhalten. also a=inverse ; a*b mod m =1.
Ich habe dazu was über den erweiterten euklidischen Algorithmus gelesen. Verstehe ihn aber nicht wirklich.
Ich hoffe ihr könnt mir helfen. Vielen Dank.
Ps: Kann eine modulare inverse Negativ sein?
Geschrieben von kiste am 21.08.2009 um 13:29:
Schau bei Wikipedia den erweiterten euklidischen Algorithmus einmal an.
Willst du das Inverse von a bezüglich m berechnen so berechne ggT(a,m) und das Inverse ist die Zahl s. Das ist so weil
![[latex]1 = \operatorname{ggT} (a,m) = sa + tm \equiv sa \mod m[/latex]](http://www.matheboard.de/latex2png/latex2png.php?1 = \operatorname{ggT} (a,m) = sa + tm \equiv sa \mod m)
Das Inverse kann natürlich auch negativ sein, es ist nicht eindeutig bis auf ein additiv Vielfaches von m
Geschrieben von J.Dylan am 23.08.2009 um 15:27:
Erstmal danke für die Antwort.
Aber wieso gilt ggt(a,m)=ggt(a mod m,m). Also wieso hat der Rest von a dividiert m wieder den gleichen größten gemeinsamen Teiler?
Geschrieben von kiste am 27.08.2009 um 09:58:
Beweise ggT(a,m) = ggT(a-m,m)
Der Rest folgt daraus.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH