wiso ist 3^100000 mod 5 = 1

wiso ist 3^100000 mod 5 = 1

$$\small{\text{ F}} \ddot{u} \small{\text{r }} 3^{100000} \mod 5 \small{\text{ kann man auch schreiben }}\\ 3^{(2*500000)} \mod 5\\ = 3^{2*(500000)} \mod 5 \\ = 9^{(500000)} \mod 5 \\ \small{\text{ F}} \ddot{u} \small{\text{r die 9 kann man auch 4 schreiben, da }} 9 \mod 5 = 4 \mod 5 \small{\text{ ist. }} \\ \small{\text{ F}} \ddot{u} \small{\text{r die 4 kann man auch -1 schreiben, da }} 4 -5 \mod 5 = -1 \mod 5 \small{\text{ ist. }} \\ = 9^{(500000)} \mod 5 = -1^{(500000)} \mod 5 \\ \small{\text{ F}} \ddot{u} \small{\text{r }} (-1)^{(500000)} \small{\text{ kann man auch }} 1^{(500000)} \small{\text{ schreiben, da der Exponent geradzahlig ist. Und }} \\ 1^{(500000)} \small{\text{ist ja nichts anderes als 1. Also }} 1 \mod 5 \\ \boxed{3^{100000} = 1 \mod 5}$$

Hallo Anonymous,

wenn man  3^100000 ausrechnen würde, bekäme man als Ergebnis eine Zahl mit   47 713  Stellen.

Die letzten Stellen  sind  ...5522000001  . Hier siehst du, dass ein Rest von  1  bleibt, wenn man diese Zahl durch 5 dividiert. 

Also :   3^100000 modulo 5 = 1

Auch   3^100 mod 5 = 1      ( das kannst du auf dem Rechner nachprüfen ! )

Gruß radix ! ( der sich über ein ok freuen würde. )