| Die letzten 4 Beiträge |
| kiste |
Beweise ggT(a,m) = ggT(a-m,m)
Der Rest folgt daraus. |
| J.Dylan |
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? |
| kiste |
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 |
| J.Dylan |
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? |
|
|
