(Wir schreiben statt „a und b haben bei Division durch m den gleichen Rest“ a ≡ (b)mod(m), wobei die Klammer entfallen kann, wenn kein Missverständnis möglich ist. Die Aufgabe lässt sich freilich auch lösen, ohne diese Schreibweise zu verwenden).
a) 3≡ 3mod7 ; 32 ≡ 2mod7; 33 = 32•3 ≡ (2•3)mod7 ≡ 6mod7; 34=33•3 ≡ (6•3)mod7 ≡ 4mod7;
35 = 34•3 ≡ (4•3)mod7 ≡ 5mod7; 36 = 35•3 ≡ (5•3)mod7 ≡ 1mod7; 37=36•3 ≡ (1•3)mod7 ≡ 3mod7
Die Siebenerreste der Potenzen der Zahl 3 sind 3, 2, 6, 4, 5, 1, ...Danach wiederholt sich dieser Zyklus. ( 36 ≡ 1mod7 ist ein Beispiel zum „kleinen Fermat“ : ap-1≡1modp, falls p eine Primzahl ist und die Zahl a kein Vielfaches von p ist)
360 = (36)10 ≡ 110mod7 ≡ 1mod7; 3320 = 3318•32 = (36)53•32 ≡ (1•32)mod7 ≡ 2mod7
31211 = 31206•35 ≡ (1•35)mod7 ≡ 5mod7 : Die gesuchten Siebenerreste sind 1, 2 und 5
b) 2 ≡ 2mod5; 22 ≡ 4mod5; 23 ≡ 3mod5 ; 24 ≡ 1mod5 . Die Fünferreste der Potenzen der Zahl 2 folgen dem Zyklus 2, 4, 3, 1, ... ( 24 ≡ 1mod5 ist wieder ein Beispiel zum „kleinen Fermat“)
212 = (24)3 ≡ 13mod5 ≡ 1mod5; 2195 = 2192•23 = (24)48•23 ≡ (1•23)mod5 ≡ 3mod5; ( Daraus folgt übrigens, dass die – gerade – Zahl 2195 (bei Darstellung im Zehnersystem) mit einer 8 enden muss). 2613 = 2612•2 ≡ (1•2)mod5 ≡ 2mod5 .
Die gesuchten Fünferreste sind 1, 3 und 2
c) Sei n eine natürliche Zahl größer als 1. Wegen (n-1)2 = n2 –2n +1 ≡ 1mod(n) gilt: Die Reste der Potenzen von (n-1) bei Division durch n folgen dem Zyklus n-1, 1, n-1, 1, ..(oder: -1,1,...). Die Potenzen der Zahl 12 haben bei Division durch 13 die Reste 12, 1, 12, ..( oder: -1,1,...)
Jede Potenz von 12 mit gerader Hochzahl hat bei Division durch 13 den Rest 1 ( z.B. gilt 122=144 = 11•13 + 1). Also hat 12384562 bei Division durch 13 den Rest 1.
Ebenso haben die Potenzen von 9 bei Division durch 10 die Reste 9,1,9,1,...( z.B. 92=81 ≡ 1mod10) . Also hat 9219 den Zehnerrest 9, d.h. die Zahl 9219 endet bei Darstellung im Zehnersystem mit der Ziffer 9 .
d) 2195 = (10log2)195 = 100,3010•195 = 1058,695
Die Zahl hätte demnach im Zehnersystem 59 Stellen.
Aber der Zehnerlogarithmus der Zahl 2 ist hier auf vier Stellen gerundet; können wir sicher sein, dass die Rundungsfehler, die daraus entstehen, dieses Ergebnis nicht ändern?
Der Wert 0,3010 stimmt auf diese vier Stellen mit dem Wert des log2 überein; man erhält 0,3010 durch Abrunden des echten Wertes, wobei abgerundet wird, indem alle Stellen von der fünften an weggelassen werden. Damit gilt 0,3010 < log2 < 0,3011. Weil die Exponentialfunktion streng monoton wachsend ist, folgt aus 0,3011•195 = 58,7145 :
1058,695 < 10log2•195 = 2195 < 1058,7145
Die Abrundung auf vier Stellen hat also das Ergebnis nicht beeinflusst: Die Zahl 2195 hat im Zehnersystem 59 Stellen.