Untersuchung sehr großer Zahlen

Hinweis: Zur Lösung benötigt man - wie auch bei einigen anderen Aufgaben dieser Seite – den folgenden Zusammenhang. Seien a, b, m natürliche Zahlen. Wenn ra, rb die Reste bezeichnen, welche sich bei Division der Zahlen a bzw. b durch m ergeben, so haben die Produkte a • b und ra•rb bei Division durch m denselben Rest: a•b ≡ (ra•rb)mod(m) ( in der Fachsprache: Die Multiplikation im Ring der Restklassen modulo m ist wohldefiniert, d.h. sie hängt nicht von der Auswahl der Repräsentanten ab). Zur Lösung des Aufgabenteiles d) sind Kenntnisse zum Rechnen mit Logarithmen erforderlich.


a) Berechnen Sie die Reste, die sich bei Division der Potenzen der Zahl 3 durch 7 ergeben. Weshalb genügt es, die Reste bis zur Potenz 36 auszurechnen? Welchen Siebener-Rest haben die Zahlen 360, 3320 und 31211 ?

b) Berechnen Sie die Reste, die sich bei Division der Potenzen der Zahl 2 durch 5 ergeben. Berechnen Sie die Fünfer-Reste der Zahlen 212, 2195 und 2613 .

c) Welcher Rest ergibt sich, wenn man 12384562 durch 13 teilt? Welches ist die Endziffer ( im Zehnersystem) der Zahl 9219 ?

d) Wie viele Stellen im Zehnersystem hat die Zahl 2195 ?


(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 ; 322mod7; 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; 224mod5; 233mod5 ; 241mod5 . 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.