Modulo

17.04.2006, 00:43

nebukadnezar

Modulo

Hallo zusammen,

ich zerbreche mir gerade über folgende Modulo-Aufgabe den Kopf:

(-10^100) mod 13

Ich weiß, dass das Ergebnis 10 sein soll, komme aber leider nicht darauf. Meine Gedankengänge waren bisher wie folgt (mit der Bitte um Berichtigung):

1) Zunächst dachte ich, es würde für den Rest keine Rolle spielen, ob ich -10^100 rechne oder einfach -10 mod 13. Entsprechend Z[13] wäre mein Ergebnis somit 3.

2) Als nächstes habe ich versucht den kleinen Fermat anzuwenden:
-10^100 mod 13
= -10^100mod12 mod 13
= -10^4 mod 13
= -10^2^2 mod 13
= 100^2 mod 13
= 4^2 mod 13
= 3

Das Ergebnis ist somit zwar identisch zu dem was ich vorher hatte, aber laut Angabe wiederum falsch. Ich würde mich sehr freuen wenn jemand meine verworrenen Gehirnwindungen gerade ziehen könnte.

Vielen Dank!

17.04.2006, 01:16

Abakus

Auf diesen Beitrag antworten »

RE: Modulo
Willkommen im Forum, Nebukadnezar,

Zitat:

Original von nebukadnezar
= -10^2^2 mod 13
= 100^2 mod 13

hier unterschlägst du das Minuszeichen, und das ist es schon.

Grüße Abakus smile

17.04.2006, 02:11

nebukadnezar

Auf diesen Beitrag antworten »

Ok, zunächst mal Danke. Ich kann nachvollziehen, dass die Lösung mit

-3 mod 13 = 10

letztlich richtig ist, wenn ich das Minuszeichen nicht eliminiere, aber ich habe wohl noch nen logischen Fehler. Was ist der Grund dafür, dass sich das Minuszeichen trotz des Quadrats nicht eliminiert? Vermutlich steh ich da grad auf der Leitung...

Gruß denn.

17.04.2006, 11:43

Abakus

Auf diesen Beitrag antworten »

RE: Modulo
So ist es vielleicht nachvollziehbarer:

$\begin{eqnarray*} -10^{100}~ mod~ 13 \end{eqnarray*}$
$\begin{eqnarray*} = (-10^{(8*12 + 4)})~ mod~ 13 \end{eqnarray*}$ // hier mal mit Klammern geschrieben
$\begin{eqnarray*} = -10^4~ mod~ 13 \end{eqnarray*}$ // Kleiner Fermatscher Satz
$\begin{eqnarray*} = -(10^2)^2~ mod~ 13 \end{eqnarray*}$
$\begin{eqnarray*} = -(10^2)*(10^2)~ mod~ 13 \end{eqnarray*}$ // Zwischenschritt
$\begin{eqnarray*} = -100^2~ mod~ 13 \end{eqnarray*}$ // '-' bleibt
$\begin{eqnarray*} = -(-4)^2~ mod~ 13 \end{eqnarray*}$ // 100 mod 13 = 9
$\begin{eqnarray*} = -16~ mod~ 13 \end{eqnarray*}$ // Zwischenschritt
$\begin{eqnarray*} = 10 \end{eqnarray*}$

Letztendlich ist $\begin{eqnarray*} -10^2 \neq (-10)^2 \end{eqnarray*}$ .

Grüße Abakus smile

17.04.2006, 12:17

nebukadnezar

Auf diesen Beitrag antworten »

RE: Modulo

Zitat:

Original von Abakus
Letztendlich ist $\begin{eqnarray*} -10^2 \neq (-10)^2 \end{eqnarray*}$ .

Nehm ich jetzt halt mal so hin. Klar, ^x hat ne stärkere Bindung als -x aber an diese Klammerung muss ich mich wohl noch gewöhnen...

Danke & Gruß

18.04.2006, 00:52

nebukadnezar

Auf diesen Beitrag antworten »

Weitere Aufgabe
Will euch nicht quälen, aber ich hab noch mal ne Aufgabe, die mir Kopfzerbrechen bereitet:

1000^999 mod 99

Ich fürchte schon es gibt dafür ne ganz einfache Regel so dass man das Ergebnis sofort sieht. Ich hatte aber mit meinen Versuchen noch keinen Erfolg:

1000^999 mod 99
= 10^999 mod 99
= 10^3*3*111 mod 99
= 10^111 mod 99
= ??

Bin für jeden Hinweis dankbar...

18.04.2006, 07:30

Auf diesen Beitrag antworten »

Du weißt doch, dass $\begin{eqnarray*} 100\equiv 1\mod 99 \end{eqnarray*}$ ist. Also ist doch folgende Aufteilung günstiger:

$\begin{eqnarray*} 10^{999} \equiv 10^{2\cdot 499+1} = 100^{499}\cdot 10\equiv 10\mod 99 \end{eqnarray*}$

P.S.: Übrigens, da du bereits fehlende Klammern angesprochen hast: Schreib besser "10^(3*3*111) mod 99" .

Neue Frage »

Antworten »

Modulo

Verwandte Themen