Multiplicative Inverse mit erweitertem euklidischem Algorithmus

16.02.2018, 15:03	Alice12	Auf diesen Beitrag antworten »
Multiplicative Inverse mit erweitertem euklidischem Algorithmus Meine Frage: Hallo zusammen, ich hätte mal eine Frage und zwar versuche ich das multiplicative inverse von 2 mod 37 zu berechnen. Meine Ideen: Ich hab als erstes den euklidischen Algorithmus berechnet, also: 37= 2* 18+1 2=12+0 ggT(2,37)=1 Und beim erweiterten hätte ich ja dann einfach 1=37-218 und ich dachte mir das multiplicative inverse wäre dann einfach 18 aber wenn ich das in ein online Rechner eingebe steht da 19. Was mach ich falsch bzw. Fehlt da noch was?
16.02.2018, 15:22	HAL 9000	Auf diesen Beitrag antworten »
Sorgfältig arbeiten beinhaltet auch, auf die Vorzeichen zu achten: Aus $\begin{eqnarray} 1=37-2\cdot 18 \end{eqnarray}$ folgt $\begin{eqnarray} 1\equiv -2\cdot 18 = 2\cdot (-18)\bmod 37 \end{eqnarray}$ . Damit ist $\begin{eqnarray} 2^{-1} \equiv -18\equiv 19\bmod 37 \end{eqnarray}$ . Alternativ hättest du dir das auch mit $\begin{eqnarray} 1=2\cdot 19-37 \end{eqnarray}$ klarmachen können.
16.02.2018, 17:20	Alice12	Auf diesen Beitrag antworten »
Hallo HAL 9000, ich verstehe leider nicht wie du darauf gekommen bist $\begin{eqnarray} 2^{-1}\equiv -18\equiv 19 mod 37 \end{eqnarray}$ Kann man zwei auf die linke Seite dividieren?
16.02.2018, 17:57	HAL 9000	Auf diesen Beitrag antworten »
$\begin{eqnarray} 1\equiv 2\cdot (-18)\bmod 37 \end{eqnarray}$ ist gleichbeutend mit $\begin{eqnarray} 2^{-1} \equiv -18\bmod 37 \end{eqnarray}$ , soweit sollte es aber klar sein. Und $\begin{eqnarray} -18\equiv 19\bmod 37 \end{eqnarray}$ folgt aus $\begin{eqnarray} -18+37=19 \end{eqnarray}$ . Das ist Modulorechnung auf absoluten Grundlagenniveau, sowas muss sitzen!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »