Rechnen modulo n

17.12.2007, 12:46

slacker2d

Rechnen modulo n

Hallo,
ich sitze gerade an Matheaufgaben und weiß nicht so recht weiter. Taschenrechner ist tabu und deshalb wird es nochmal schwerer...

Die Aufgaben sehen in etwa so aus: $\begin{eqnarray*} 37^{25} (mod 19) \end{eqnarray*}$

Wie kann ich an die Aufgabe ran gehen? verwirrt

17.12.2007, 13:00

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 37 = 2\cdot 19-1 \equiv -1\mod 19 \end{eqnarray*}$

Damit ist die Sache ratz-fatz erledingt.

17.12.2007, 13:22

slacker2d

Auf diesen Beitrag antworten »

also das

$\begin{eqnarray*} -1\ mod\ 19 = 18 \end{eqnarray*}$

ist verstehe ich, aber wie komme ich gedanklich auf

$\begin{eqnarray*} 37 = 2\cdot19 - 1 \end{eqnarray*}$

???

17.12.2007, 13:25

Auf diesen Beitrag antworten »

Es ist doch ganz natürlich, bei Potenzen $\begin{eqnarray*} a^b\mod m \end{eqnarray*}$ für die Basis $\begin{eqnarray*} a \end{eqnarray*}$ gemäß dem Modul $\begin{eqnarray*} m \end{eqnarray*}$ einen betragsmäßig möglichst kleinen Repräsentanten zu wählen, und das ist hier nun mal die -1.

17.12.2007, 13:40

Philipp Imhof

Auf diesen Beitrag antworten »

Zitat:

Original von slacker2d
also das

$\begin{eqnarray*} -1\ mod\ 19 = 18 \end{eqnarray*}$

ist verstehe ich

Ich glaube, du hast Arthur Dents Tipp falsch verstanden. Er meinte nicht, du sollest -1 mod 19 rechnen, sondern dass man 37 (mod 19) genauso gut als -1 (mod 19) schreiben kann.

17.12.2007, 14:14

slacker2d

Auf diesen Beitrag antworten »

Ja, stimmt. Naja ich hab da eh einige Lücken fürchte ich. Jetzt ist mir zwar klar, was ich bei

$\begin{eqnarray*} a^b\ (mod\ n) \end{eqnarray*}$

wenn a > n tun muss/kann aber bei a < n rätsel ich gerade noch...

17.12.2007, 14:44

Auf diesen Beitrag antworten »

Zitat:

Original von slacker2d
aber bei a < n rätsel ich gerade noch...

Was ist los: Angst vor negativen Zahlen? Die Regel

$\begin{eqnarray*} x\equiv y\mod m \quad\Longrightarrow\quad x^n\equiv y^n\mod m \end{eqnarray*}$

gilt für beliebige ganze Zahlen $\begin{eqnarray*} x,y \end{eqnarray*}$ , nicht nur natürliche. Und $\begin{eqnarray*} x\equiv y\mod m \end{eqnarray*}$ heißt nichts weiter, dass $\begin{eqnarray*} (x-y) \end{eqnarray*}$ durch $\begin{eqnarray*} m \end{eqnarray*}$ teilbar ist.

17.12.2007, 16:23

slacker2d

Auf diesen Beitrag antworten »

Fermat hin oder her, Definition des Moduls und was sonst noch so gebraucht wird, ich verstehe das nicht:

$\begin{eqnarray*} 17^{521}\ mod\ 23 = 15 \end{eqnarray*}$

$\begin{eqnarray*} 17\ mod\ 23 = 17 \end{eqnarray*}$

verwirrt

17.12.2007, 16:38

Auf diesen Beitrag antworten »

Zitat:

Original von slacker2d
Fermat hin oder her

Nicht "hin oder her", sondern anwenden! Das reduziert die Rechnerei schon mal ein wenig.

17.12.2007, 20:32

slacker2d

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 521 = 499 + (23 - 1) = 477 + 2\cdot(23 - 1) = \ldots = 15 + 23\cdot(23 - 1) \end{eqnarray*}$

$\begin{eqnarray*} 17^{521}\ mod\ 23 \equiv17^{15} \cdot (17^{23})^{(23-1)}\equiv 15\ mod\ 23 \end{eqnarray*}$

Kann man das so durchgehen lassen? Und sind die Gleichheits/Kongruenzzeichen korrekt, da bin ich mir total unsicher ?!

17.12.2007, 20:45

Auf diesen Beitrag antworten »

Ist Ok. Üblicherweise schreibt man aber das mod 23 nur einmal pro Gleichungs- besser gesagt Kongruenzkette, nämlich rechts am Ende.

Neue Frage »

Antworten »

Rechnen modulo n

Verwandte Themen