Hallo,

du möchtest folgende Gleichung zeigen:

$$a^n\mod b=(a\mod b)^n\mod b.$$

Wir benutzen Induktion. Sei \(n=1\). Dann gilt:

$$a\mod b=(a\mod b)\mod b$$

Es gelte also:

$$a^n\mod b=(a\mod b)^n\mod b$$

für ein festes \(n\in\mathbb{N}\). Wir gehen zu \(n+1\) über:

 \(\begin{equation}\begin{split}(a\mod b)^{n+1}\mod b&=(a\mod b)\cdot(a\mod b)^n\mod b\nonumber\\&=(a\mod b)\cdot a^n\mod b\nonumber\\&=a\cdot a^n\mod b\nonumber\\&=a^{n+1}\mod b\nonumber\end{split}\end{equation}\)

Dabei wurde im vorletzten Schritt die Gleichung:

$$(x\mod z)\cdot(y\mod z)=xy\mod z$$

benutzt. Wenn dir diese Gleichung unklar ist, dann kannst du dir den Beweis dafür anschauen:

Sei \(x=a+bz\) und \(y=c+dz\). Dann gilt

\(\begin{equation}\begin{split}xy\mod z&=(a+bz)(c+dz)\mod z\\&=(ac+adz+bcz+bdz^2)\mod z\\&=ac\mod z+adz\mod z+bcz\mod z+bdz^2\mod z\\&=a\cdot c\mod z\\&=(x\mod z)\cdot(y\mod z)\mod z\end{split}\end{equation}\)

Ich hoffe dir ist es jetzt klar! :)