Reste von Potenzen beim ganzzahligen Teilen

Kürzlich zeigte ich in einem Artikel, dass es keine Quadratzahl gibt, die ganzzahlig durch drei geteilt einen Rest zwei hat. Dafür ordnete ich zunächst alle natürlichen Zahlen in eine von drei Klassen ein – je nachdem welchen Rest 0, 1 oder 2 sie bei der Division durch drei aufweisen. Es zeigte sich nämlich, dass der Rest einer durch drei geteilten Quadratzahl allein vom Rest ihrer durch drei geteilten Wurzel abhängt.

Auf dieser Seite möchte ich diese Einsicht gewissermaßen auf alle natürlichen Exponenten und Divisoren verallgemeinern und dann gerade Exponenten noch einmal genauer betrachten.

Symbole und ein erster Satz

Man nehme eine Zahl b, teile sie durch den Divisor m und nenne das Ergebnis a Rest r. Dann ist quasi als Umkehr dieses Vorganges b = r + m ⋅ a. Die Operation, welche beim ganzzahligen Teilen nur den Rest ausgibt, soll modulo heißen und wird durchs Zeichen „mod“ repräsentiert, sodass b mod m = r. Betrachtet werden b, a und r aus dem Bereich der natürlichen Zahlen einschließlich null. r ist immer kleiner als m, welches wie ein Exponent n aus den natürlichen Zahlen ohne null stammt.

Satz 1, vorerst eine Behauptung, lautet mit diesen Voraussetzungen:

oder anders ausgedrückt:

Nach einer Vorüberlegung wird Satz 1 bewiesen.

Vorüberlegung

Wenn b geteilt durch m gleich a Rest r ist, was ist dann (b + m) geteilt durch m? Offenbar passt in die Summe genau ein m mehr hinein, sodass das Ergebnis a + 1 Rest r lauten muss. Dann ist (b + m + m) geteilt durch m gleich a + 2 Rest r und mit einem natürlichen c allgemein (b + m ⋅ c) geteilt durch m gleich a + c Rest r. Beachte: Der Rest ändert sich nicht, wenn man vor dem Teilen ein Vielfaches des Divisors m hinzuaddiert. Man kann also schreiben:

Beweis für Satz 1

Zunächst kann man wegen b = r + m ⋅ a schreiben:

Mit dem Binomischen Lehrsatz lässt sich die rechte Seite der Gleichung auch so darstellen:

Aus der Summe ziehe ich nun den ersten Summanden mit k = 0 heraus:

Vereinfacht steht da:

Ein m kann ich getrost „ausklammern“, denn dank k ≥ 1 ist sichergestellt, dass auch ein Exponent k − 1 nicht negativ wird und somit keine gebrochene Zahl ins Spiel kommt:

Nun werden beide Seiten ganzzahlig durch m geteilt.

In der Vorüberlegung habe ich gezeigt, dass sich der Rest einer ganzzahligen Division nicht ändert, wenn man vor dem Teilen ein Vielfaches des Divisors hinzuaddiert. Genau das passiert hier in der großen Klammer: $m\cdot\sum_{k=1}^n\binom{n}{k}r^{n-k}m^{k-1}a^k$ ist ein Vielfaches von m und trägt somit nichts zum Rest der Division bei. Es bleibt:

… was zu beweisen war. Um den Rest einer Potenz bei ganzzahliger Divison zu ermitteln, braucht man also nicht die Basis zu kennen, sondern nur den Rest jener Basis bei derselben ganzzahligen Division.

Folgen

Setzt man für b nacheinander null und alle natürlichen Zahlen ein, ergibt sich aus der Vorüberlegung, dass b mod m sich stets nach m Zahlen wiederholt. Ein Beispiel für m = 5 und b von 0 bis 10:

Aus Satz 1 ergibt sich, dass auch $b^n\bmod m$ sich alle m Zahlen wiederholt. Hier Beispiele, bei denen für den Exponenten n einmal 2 und einmal 3 eingesetzt wurde:

Mehr Symmetrie bei geradem Exponenten

Bei ganzzahliger Division einer Potenz mit geradem Exponenten und Divisor m wiederholt sich das Ergebnis nicht nur alle m Zahlen. Man kann die sich wiederholenden Zahlen auch rückwärts genauso wie vorwärts lesen. In der zweiten Zeile des vorigen Beispiels mit dem Exponenten 2 ist das der Fall.

Satz 2 besagt:

Beweis für Satz 2

Zunächst definiere ich s als Rest einer bestimmten ganzzahligen Division:

Laut der Vorüberlegung gilt, weil m ⋅ (m − 2r) ein Vielfaches des Divisors m ist, dann auch:

Nun stelle ich aus der Selbstverständlichkeit heraus, dass Gleiches gleich ist, dies fest:

Laut Satz 1 kann ich in diese Gleichung anstelle von s auch eine andere Zahl einsetzen, die bei Division durch m den Rest s hat. Dafür hatte ich eben zwei Kandidaten notiert, einerseits $r^2$ und andererseits $r^2+m\cdot(m-2r)$. Beide dürfen sich nützlich machen, jeder auf einer Seite:

Die innere Klammer auf der rechten Seite ausmultipliziert ergibt:

Mit den binomischen Formeln lässt sich das neu zusammenfassen:

Nun kann ich mit den Regeln der Potenzrechnung die verschachtelten Potenzen vereinfachen, indem ich die Exponenten multipliziere:

… was zu beweisen war.