0 Daumen
93 Aufrufe

Aufgabe:

Berechne die letzten vier Ziffern der Zahl 22020.


Problem/Ansatz:

Normalerweise würde ich bei so einer Aufgabe mit Restklasse 10, etc. arbeiten, aber das scheint mir bei den letzten vier Ziffern nicht der richtige Weg. Wie könnte man das sonst machen? Vielen Dank!!!

von

Damit bin ich bisher nicht weitergekommen, weil es einfach zu viele Restklassen gibt.

3 Antworten

+1 Daumen
 
Beste Antwort

Hallo Paul,

Damit bin ich bisher nicht weitergekommen, weil es einfach zu viele Restklassen gibt.

Ja 10000 ist schon ein wenig unhandlich und \(\varphi(10000) = 4000\) - hilft hier auch nicht wirklich weiter. Wenn Wolfram-Alpha keine Option ist (s. Antwort von Monty) dann mache Dir eine Tabelle, die auf folgenden Algorithmus beruht.

Man stellt die Zahl dar als \(a_i \cdot b_i^{e_i} \) mit \(a_0=1\), \(b_0=2\) und \(e_0=1024\). Und außerdem interessieren uns hier nur die letzten 4 Stellen also \(\mod 10000\). Anschließend verkleinert man sukzessive den Exponenten wie folgt (hier ist \(m=10000\))$$a_{i+1} \equiv \begin{cases} a_i & e_i \equiv 0 \mod 2 \\ a_i \cdot b_i &e_i \equiv 1 \mod 2\end{cases} \mod m\\ b_{i+1} \equiv b_i^2 \mod m \\ e_{i+1} = \left\lfloor \frac {e_i}2 \right\rfloor $$das macht man solange bis \(e_n=0\) ist. Dann steht dort \(a_n \cdot b_n^0\) und damit das Ergebnis in \(a_n\).

Im konkreten Fall von \(2^{2020} \mod 10000\) sieht die Tabelle so aus: $$\begin{array}{rrr}a_i& b_i& e_i\\ \hline 1& 2& 2020\\ 1& 4& 1010\\ 1& 16& 505\\ 16& 256& 252\\ 16& 5536& 126\\ 16& 7296& 63\\ 6736& 1616& 31\\ 5376& 1456& 15\\ 7456& 9936& 7\\ 2816& 4096& 3\\ 4336& 7216& 1\\ 8576& & 0\end{array}$$Das Ergebnis ist$$2^{2020} \equiv 8576 \mod 10000$$Rechnen lässt sich das mit einem normalen Taschenrechner oder einfacher mit einem Tabellenkalkulationsprogramm. Und die ersten vier Zeilen notfalls im Kopf ;-)

vor von 29 k

Sehr schöne Lösung!

Daumen hoch!

:-)

Danke :-)              .

0 Daumen

Wie wäre es mit der Restklasse mod 10000 ?

von 204 k 🚀
0 Daumen

Erst einmal Onkel Wolfram fragen. ;-)

2^{2020}=


blob.png

von 15 k

Um jetzt diese Zahl bitte in Worten! :)

Achttausendfünfhundertsechsundsiebzig

8;5;7;6

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community