Zahlentheorie/Berechnung Dezimalstellen

23.10.2018, 14:55

InaAldi

Zahlentheorie/Berechnung Dezimalstellen

Hallo Zusammen,

es sollen die letzten 3 Ziffern der Zahl 7^9999 berechnet werden.

Als Hinweis dazu steht: 7*11*13=1001 und „kleiner Satz von Fermat“

Ich weiß, dass ich wegen der letzten 3 Ziffern mod(1000) rechnen muss. Die Primfaktorzerlegung bringt mich jedoch eher durcheinander als weiter.

Vielen Dank für jede Hilfe

Ina

23.10.2018, 16:44

HAL 9000

Auf diesen Beitrag antworten »

Mit Carmichael-Funktion $\begin{eqnarray*} \lambda \end{eqnarray*}$ gilt

$\begin{eqnarray*} 7^{\lambda(1000)} = 7^{\operatorname{kgV}(100,2)} = 7^{100}\equiv 1\bmod 1000 \end{eqnarray*}$

(kann man sich auch mit der Eulerschen $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion getrennt nach Primfaktorpotenzen $\begin{eqnarray*} 5^3 \end{eqnarray*}$ und $\begin{eqnarray*} 2^3 \end{eqnarray*}$ klarmachen), damit ist $\begin{eqnarray*} 7^{9999} \equiv 7^{100\cdot 100}\cdot 7^{-1}\bmod 1000 \end{eqnarray*}$ .

Der Hinweis $\begin{eqnarray*} 7*11*13=1001 \end{eqnarray*}$ kann nun nützlich sein, um dieses $\begin{eqnarray*} 7^{-1} \end{eqnarray*}$ zu bestimmen. Augenzwinkern

24.10.2018, 11:32

InaAldi

Auf diesen Beitrag antworten »

Vielen Dank für Deine Hilfe!

Dann müsste sich doch Folgendes ergeben:

$\begin{eqnarray*} 7^{1000} \equiv 1mod(1000) \Rightarrow 1^{1000} \equiv 1 mod (1000)\Rightarrow 1\equiv 1mod(1000) \end{eqnarray*}$

Demnach müssten die letzten Ziffern dann doch 001 sein, oder?!

24.10.2018, 12:18

InaAldi

Auf diesen Beitrag antworten »

Sorry, ich hatte mich verschrieben.

Gilt nicht, dass sie letzten Ziffern 001 sind wegen

$\begin{eqnarray*} 7^{9.999}=\left(7^{10} \right) ^{1000} \cdot 7^{-1} \equiv 1mod(1000) \end{eqnarray*}$

Zudem habe ich noch gesehen, dass auch für die Zahlen

$\begin{eqnarray*} 11^{9.999} \end{eqnarray*}$ und $\begin{eqnarray*} 13^{9.999} \end{eqnarray*}$ die letzten drei Ziffern bestimmt werden sollen.

Da müsste jeweils „001“ als Endziffern rauskommen.

Wenn ich mich nicht vertan habe, ergibt sich bei den (Prim-)Zahlen 7, 11 und 13 auch das inverse Element in diesem Fall aus dem Produkt der jeweils anderen beiden Zahlen. Vielleicht war der Hinweis mit der „1001“ hierauf bezogen...

24.10.2018, 12:42

HAL 9000

Auf diesen Beitrag antworten »

Ich sehe gerade, ich hatte oben einen Term vergessen, die Zeile

Zitat:

Original von HAL 9000
$\begin{eqnarray*} 7^{9999} \equiv 7^{100\cdot 100}\cdot 7^{-1}\bmod 1000 \end{eqnarray*}$ .

ist zwar nicht falsch, aber sollte eigentlich noch weitergehen: $\begin{eqnarray*} 7^{9999} \equiv 7^{100\cdot 100}\cdot 7^{-1}\equiv 7^{-1}\bmod 1000 \end{eqnarray*}$ .

Wir müssen also "nur" $\begin{eqnarray*} x=7^{-1}\bmod 1000 \end{eqnarray*}$ bestimmen, also die Kongruenz $\begin{eqnarray*} 7\cdot x\equiv 1\bmod 1000 \end{eqnarray*}$ lösen. Wirklich keine Idee, wie dabei $\begin{eqnarray*} 7\cdot (11\cdot 13) = 1001\equiv 1\bmod 1000 \end{eqnarray*}$ helfen könnte? Augenzwinkern

24.10.2018, 13:49

InaAldi

Auf diesen Beitrag antworten »

Wenn ich das richtig sehe, müsste die Lösung so aussehen, wenn ich Deinen Hinweis richtig verstehe:

$\begin{eqnarray*} 7\cdot 11\cdot 13= 1001\equiv1mod(1.000) \end{eqnarray*}$

Aber wie schreibe ich das denn korrekt auf?

Ich würde zunächst folgendermaßen vorgehen, weil dies für alle Zahlen gilt:
Zunächst gilt allgemein $\begin{eqnarray*} x^{1000} \equiv1mod(1.000) \end{eqnarray*}$
Somit gilt auch $\begin{eqnarray*} \left(x^{1000}\right)^{n} \equiv1mod(1.000) \end{eqnarray*}$

Für die einzelnen Zahlen gilt dann:
$\begin{eqnarray*} \left(7^{1000}\right)^{10} \cdot 7^{-1} \equiv1\cdot 7^{-1} mod(1.000) \end{eqnarray*}$

Allerdings weiß ich nicht so recht, wie ich das mit dem Produkt aus 7, 11 und 13 mod (1000) richtig aufführen soll.😕

24.10.2018, 13:58

HAL 9000

Auf diesen Beitrag antworten »

Die Antwort, auf die ich versucht habe hinzudeuten, ist schlicht und einfach $\begin{eqnarray*} x = 11\cdot 13 = 143 \end{eqnarray*}$ . Augenzwinkern

24.10.2018, 14:22

InaAldi

Auf diesen Beitrag antworten »

Also würdest Du das auch nur so hinschreiben...

Vielen Dank!!! Wink

24.10.2018, 19:11

HAL 9000

Auf diesen Beitrag antworten »

Ergänzend noch eine Korrektur:

Zitat:

Original von InaAldi
Zunächst gilt allgemein $\begin{eqnarray*} x^{1000} \equiv1mod(1.000) \end{eqnarray*}$

Es gilt bereits (s.o.) $\begin{eqnarray*} x^{100} \equiv 1 \bmod 1000 \end{eqnarray*}$ , aber nicht "allgemein", sondern nur für alle zu 1000 teilerfremden Zahlen $\begin{eqnarray*} x \end{eqnarray*}$ , einfacher formuliert: Für alle Zahlen $\begin{eqnarray*} x \end{eqnarray*}$ , die weder durch 2 noch durch 5 teilbar sind.

Neue Frage »

Antworten »

Zahlentheorie/Berechnung Dezimalstellen

Verwandte Themen