Modulo - Auflösen

21.05.2009, 20:11

NatürlicheZahl

Modulo - Auflösen

Hallo,

wie kann ich Folgendes nach d auflösen:

17d mod 616 = 1

(Wenn man 17d durch 616 teilt soll sich ein Rest von 1 ergeben)

Danke!

21.05.2009, 20:13

Auf diesen Beitrag antworten »

Dafür gibt es den Erweiterten Euklidischen Algorithmus (EEA). Augenzwinkern

21.05.2009, 20:16

NatürlicheZahl

Auf diesen Beitrag antworten »

Okay,

ich habs mir schnell vom Computer berechnen lassen Big Laugh

Es ist d = 145.

Danke!

21.05.2009, 20:46

NatürlicheZahl

Auf diesen Beitrag antworten »

Wie kann ich sowas großes ausrechnen:

c = 8^23 mod 40 ??

Selbst mein Computer hat mit 8^23 ein gewältiges Problem böse

21.05.2009, 20:53

Cordovan

Auf diesen Beitrag antworten »

Du kannst sukzessive Zweierpotenzen berechnen: 8, 8^2, 8^4=(8^2)^2 und so weiter. Danach setzt du 23 mithilfe der berechneten Zweierpotenzen zusammen: 23=16+4+2+1. Dann musst du nur quadrieren und es kommen keine hohen Zahlen mehr vor.

Cordovan

21.05.2009, 21:16

NatürlicheZahl

Auf diesen Beitrag antworten »

Wie würde das für 8^23 aussehen?

$\begin{eqnarray*} ((8^2) \cdot 8)^2 \cdot 8)^2.... \end{eqnarray*}$

Wie oft muss ich das machen? Habs nicht ganz verstanden...

21.05.2009, 21:42

Bjoern1982

Auf diesen Beitrag antworten »

Wenns dir eh nur aufs schnelle Ergebnis ankommt gibs in Google ein oder noch besser benutze den guten alten Windows Taschenrechner, der kann da einiges smile

21.05.2009, 21:54

NatürlicheZahl

Auf diesen Beitrag antworten »

Danke

22.05.2009, 08:44

Cordovan

Auf diesen Beitrag antworten »

Zitat:

Wie würde das für 8^23 aussehen?

$\begin{eqnarray*} 8\equiv 8 \end{eqnarray*}$
$\begin{eqnarray*} 8^2\equiv 24 \end{eqnarray*}$
$\begin{eqnarray*} 8^4\equiv24^2\equiv16 \end{eqnarray*}$
$\begin{eqnarray*} 8^8\equiv16^2\equiv16 \end{eqnarray*}$
$\begin{eqnarray*} 8^{16}\equiv16^2\equiv16 \end{eqnarray*}$

Dann berechnest du
$\begin{eqnarray*} 8^{23}\equiv8^{16+4+2+1}\equiv16\cdot16\cdot24\cdot8\equiv 32 \end{eqnarray*}$ .

Cordovan

22.05.2009, 09:24

Bjoern1982

Auf diesen Beitrag antworten »

Ich wär zu faul mir den Taschenrechner zu schnappen und würds von Hand machen:

$\begin{eqnarray*} 8^{23} \mod\ 40 \end{eqnarray*}$

Euler-Fermat lässt sich noch nicht anwenden, da ggt(8;40)=8 ungleich 1

CRS liefert

$\begin{eqnarray*} x \equiv\ 8^{23} \mod\ 8\ (1) \end{eqnarray*}$

$\begin{eqnarray*} x \equiv\ 8^{23} \mod\ 5\ (2) \end{eqnarray*}$

Aus (2) folgt nun wegen $\begin{eqnarray*} \varphi(5)=4 \end{eqnarray*}$ durch Euler-Fermat $\begin{eqnarray*} (8^4)^6 \cdot 8^{-1} \equiv\ 2\ mod\ 5 \end{eqnarray*}$ da $\begin{eqnarray*} 8 \cdot 2=16 \equiv\ 1\ mod\ 5 \end{eqnarray*}$

Da x wegen (1) eine durch 8 teilbare Zahl sein muss folgt $\begin{eqnarray*} 2-2 \cdot 5=-8 \equiv\ 32\ mod\ 40 \end{eqnarray*}$

22.05.2009, 09:47

Auf diesen Beitrag antworten »

Und noch eine Möglichkeit, damit man sieht, wieviele Wege nach Rom führen

$\begin{eqnarray*} 8^1 & \equiv & 8 \bmod 40 \\ 8^2 & \equiv & 24 \bmod 40 \\ 8^3 & \equiv & 32 \bmod 40 \\ 8^4 & \equiv & 16 \bmod 40 \\ 8^5 & \equiv & 8 \bmod 40 \end{eqnarray*}$

Damit sind wir in einer Periode der Länge 4 angelangt, es gilt somit

$\begin{eqnarray*} 8^{23} = 8^{4\cdot 5+3} \equiv 8^3 \equiv 32 \bmod 40 \end{eqnarray*}$ .

Neue Frage »

Antworten »

Modulo - Auflösen

Verwandte Themen