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 ;-)
