Endziffern und verschachtelte Potenzen

Potenzreste schnell berechnen · Abschnitt 19 von 64

Definition

Endziffern als Modul

Die letzte Ziffer entspricht dem Rest modulo 10, die letzten zwei Ziffern dem Rest modulo 100 und die letzten drei Ziffern dem Rest modulo 1000.

Gelöstes Beispiel

Drei Endziffern

Ergibt eine Rechnung $a^n\equiv1\pmod{1000}$ , so lauten die letzten drei Ziffern 001. Der Endblock besitzt immer genau drei Stellen.

Strategie

Verschachtelte Potenzen von außen lesen

Bei $a^{b^c}\pmod m$ wird zuerst geklärt, welche Information über den Exponenten $b^c$ genügt. Eine bekannte Potenz mit Rest 1 kann den äußeren Exponenten in Blöcke zerlegen.

Hinweis für Begleitende

Noch ohne Fermat und Euler

Wiederholtes Quadrieren benötigt keine Teilerfremdheit und keinen allgemeinen Potenzsatz. Fermat, Euler und die Ordnung einer Restklasse folgen systematisch in Teil IV.