Letzten drei Dezimalstelle berechnen

26.02.2013, 16:35

JuPee

Letzten drei Dezimalstelle berechnen

Hallo zusammen,

ich will die letzten drei Dezimalstellen von $\begin{eqnarray*} 7^{9999} \end{eqnarray*}$ berechnen.

Meine Idee:

Ich muss also $\begin{eqnarray*} 7^{9999}\equiv x \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ berechnen.

Da der $\begin{eqnarray*} ggT(7,1000) = 1 \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(1000) = 400 \end{eqnarray*}$ ist, weiß ich nach dem Satz von Euler, dass $\begin{eqnarray*} 7^{400}\equiv 1 \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ ist.

Daraus folgt: $\begin{eqnarray*} 7^{9999}= \left(7^{400} \right)^{24} \cdot 7^{399} \equiv 1^{24}\cdot 7^{399} \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ .

D.h. ich muss jetzt $\begin{eqnarray*} 7^{399} \equiv x \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ berechnen. Jedoch klappt dies nicht nach den altbewährten Vorgehensweisen.

Normalerweise würde ich $\begin{eqnarray*} 7^{399} \equiv 7^{256}\cdot 7^{128}\cdot 7^{8}\cdot 7^{4} \cdot 7^{2} \cdot 7^{1} \end{eqnarray*}$ aufteilen und die einzelnen Kongruenzen berechnen.

Da kommt aber raus: $\begin{eqnarray*} 7^{399} \equiv 601\cdot 801 \cdot 801\cdot 401 \cdot 49 \cdot 7 \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ .

Diese Zahl sprengt aber leider auch meinen Taschenrechner ... Kann mir einer weiterhelfen?

26.02.2013, 16:53

captain obvious

Auf diesen Beitrag antworten »

Hallo,

beachte:
$\begin{eqnarray*} 7^{399}= 7^{400-1} \end{eqnarray*}$
Alternativ kannst du bei deiner Rechnung immer nur zwei zahlen multiplizieren und dann vereinfachen.

26.02.2013, 17:16

JuPee

Auf diesen Beitrag antworten »

An die erste Möglichkeit habe ich auch schon gedacht, aber ich weiß nicht was $\begin{eqnarray*} 7^{-1} \equiv x \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ ist.

Die zweite Idee hat mich aber zur Lösung gebracht. Danke smile

Ich habe aber direkt noch eine Frage:

Und zwar soll ich die letzte Ziffer von $\begin{eqnarray*} 4713^{815^{42} } \end{eqnarray*}$ bestimmen.

Dabei habe ich zunächst die letzte Zahl von $\begin{eqnarray*} 4713^{815 } \end{eqnarray*}$ berechnet, die $\begin{eqnarray*} 7 \end{eqnarray*}$ wäre, und dann die von $\begin{eqnarray*} 7^{42} \end{eqnarray*}$ , die $\begin{eqnarray*} 9 \end{eqnarray*}$ ist. Leider ist dies aber das falsche Ergebnis.

Hast du dafür auch einen Tipp oder Hinweis?

26.02.2013, 17:33

captain obvious

Auf diesen Beitrag antworten »

Zitat:

Original von JuPee
An die erste Möglichkeit habe ich auch schon gedacht, aber ich weiß nicht was $\begin{eqnarray*} 7^{-1} \equiv x \end{eqnarray*}$ mod $\begin{eqnarray*} 1000 \end{eqnarray*}$ ist.

Du willst mir doch nicht ernsthaft erzählen, dass du den erweiterten euklidischen Algorithmus nicht kennst, oder? (wobei sich hier die Sache wegen 10³ sogar noch einfacher machen könnte)

Zum Rest:
Konventionen/ Rechenregeln zur Exponentation beachten ist hilfreich:
$\begin{eqnarray*} a^{b^c} \neq (a^b)^c \end{eqnarray*}$

26.02.2013, 18:04

JuPee

Auf diesen Beitrag antworten »

Doch, den erweiterten euklidischen Algorithmus kenne ich, damit kann ich aber in der Situation nichts anfangen -.-

Ahja, ok ... Das ergibt Sinn. Und wie gehe ich dabei vor?

26.02.2013, 18:15

captain obvious

Auf diesen Beitrag antworten »

Zitat:

Doch, den erweiterten euklidischen Algorithmus kenne ich, damit kann ich aber in der Situation nichts anfangen -.-

Die erste Teil dieses Satzes widerspricht dem Zweiten. Die Bestimmung von Inversen modulo n ist die Anwendung des erweiterten euklidischen Algorithmus.

Zitat:

Ahja, ok ... Das ergibt Sinn. Und wie gehe ich dabei vor?

So wie du auch bei der anderen Aufgabe vorgegangen bist: Reduktion des Exponenten modulo $\begin{eqnarray*} \phi (10) \end{eqnarray*}$ .

P.S. Zwar nicht hier aber generell für diese Art von Aufgaben ist die Carmichael-Funktion sehr nützlich.

Neue Frage »

Antworten »

Letzten drei Dezimalstelle berechnen

Verwandte Themen