Zahlentheorie: Inverse bestimmen

13.10.2005, 00:02	nixraffer	Auf diesen Beitrag antworten »
Zahlentheorie: Inverse bestimmen Hi, kann mir jemand vielleicht erklären, wie man in der Zahlentheorie die Inverse bestimmt? Also beispielsweise was ist die Inverse von "7 mod 31"? Kann man sicherlich raten (7^-1 = 9), aber wie kann ich die ERRECHNEN? Danke und viele Grüße, Thomas
13.10.2005, 06:38	Leopold	Auf diesen Beitrag antworten »
Bei kleinen Moduln ist Probieren sicher eine gute Methode. Oder man rechnet mit Potenzen. Für eine Primzahl $\begin{eqnarray} p \end{eqnarray}$ gilt nämlich modulo $\begin{eqnarray} p \end{eqnarray}$ : $\begin{eqnarray} a^{p-1} \equiv 1 \ \ \Leftrightarrow \ \ a^{-1} \equiv a^{p-2} \end{eqnarray}$ In unserem Beispiel könnte man so rechnen (alle Kongruenzen modulo 31): $\begin{eqnarray} 7^{-1} \equiv 7^{29} \end{eqnarray}$ $\begin{eqnarray} 7^{29} \equiv \left( 7^5 \right)^5 \cdot 7^4 \end{eqnarray}$ $\begin{eqnarray} 7^2 \equiv 7 \cdot 7 \equiv 18 \end{eqnarray}$ $\begin{eqnarray} 7^3 \equiv 7^2 \cdot 7 \equiv 18 \cdot 7 \equiv 2 \end{eqnarray}$ $\begin{eqnarray} 7^4 \equiv 7^3 \cdot 7 \equiv 2 \cdot 7 \equiv 14 \end{eqnarray}$ $\begin{eqnarray} 7^5 \equiv 7^4 \cdot 7 \equiv 14 \cdot 7 \equiv 5 \end{eqnarray}$ $\begin{eqnarray} \left( 7^5 \right)^5 \equiv 5^5 \equiv 25 \end{eqnarray}$ $\begin{eqnarray} 7^{-1} \equiv \left( 7^5 \right)^5 \cdot 7^4 \equiv 25 \cdot 14 \equiv 9 \end{eqnarray}$ Und natürlich geht es auch immer mit dem Standardverfahren, dem Euklidischen Algorithmus.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »