Warum Restzyklen entstehen

Restzyklen, Perioden und Vorperioden · Abschnitt 21 von 64

Intuition

Endlich viele Zustände

Wenn du immer wieder mit derselben Zahl multiplizierst und den Rest nimmst, musst du irgendwann auf einen alten Rest stoßen. Dann beginnt ein Zyklus.

Satz

Schließliche Periodizität

Für jedes ganze $a$ und jedes $m>0$ ist die Folge $a,a^2,a^3,\ldots$ modulo $m$ schließlich periodisch.

Beweis

Gleicher Zustand, gleiche Zukunft

Aus $a^i\equiv a^j\pmod m$ mit $i<j$ folgt nach Multiplikation mit $a^k$ stets $a^{i+k}\equiv a^{j+k}$ . Der Abstand $j-i$ wiederholt sich daher ab $i$ .

Gelöstes Beispiel

Zweierpotenzen modulo 9

Die Reste $2,4,8,7,5,1$ wiederholen sich. Der Zyklus beginnt sofort und besitzt Länge 6.