Was ist der Rest von 7^40 geteilt durch 400?
Don Alvaros Antwort hat mich doch nicht ruhen lassen. Zunächst mal vielen Dank; er ist der erste, dem es gelungen ist, ^mich zu motivieren, mir mal die Eulersche Phifunktion gründlich anzusehen. Phi ist definiert als
Phi ( n ) = ° G_n ( 1 )
Von Anfang an verstand ich nicht, worauf Alvaro eigentlich hinaus will. Denn es gilt ja
Phi ( 40 ) = 16 ( 2a )
und folglich
Phi ( 400 ) = 10 * 16 = 160 ( 2b )
Und von Daher bleibt also voll unerfindlich, wieso Alvaro mit dem ( viel zu kleinemn ) Wert ( 2a ) rechnet statt mit ( 2b )
Ich habe mir daher die ganze Chose in Wolfram mal näher angesehen. Im Einzelfall taugt die Eulerformel ja nicht viel, weil sie eine viel zu schlechte Abschätzung gibt. Im Einzelfall folgt ja nur
° n | ° G_n ( 3a )
Folglich
° 7 | ° G_400 ( 3b )
noch dazu in diesem grotesken Fall, wo lt. Wolfram
° 7 << ° G_400 ( 3c )
Es ist nämlich ° 7 = 4 , weil
7 ^ 4 = 49 ² = 2 401 = 1 mod 400 ( 4a )
Und damit dürfte sich die Frage trivial erledigen:
7 ^ 40 = ( 7 ^ 4 ) ^ 10 = 1 ^ 10 = 1 mod 400 ( 4b )