Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Informatik in der Schule (http://www.informatikerboard.de/board/board.php?boardid=21)
--- Zeige, dass 41|(17^1000)-1 (http://www.informatikerboard.de/board/thread.php?threadid=3356)
Geschrieben von Linsane am 13.12.2016 um 18:21:
Zeige, dass 41|(17^1000)-1
Meine Frage:
Guten Tag,
Ich soll zeigen das folgendes gilt:
41|(17^1000)-1.
Den Lösungsweg dazu hab ich und verstehe diesen auch größtenteils. Nur habe ich zu einer Stelle eine konkrete Frage. Die Lösung der Aufgabe beginnt mit der Umformung zu:
(17^1000) mod 41 = 1 mod 41
Warum darf man diese Umformung ausführen?
Meine Ideen:
Der komplette Lösungsweg funktioniert dann nach der Umformung folgendermaßen:
((17^40)^25) mod 41 = 1 mod 41
<-> (17^40 mod 41)^25 mod 41 = 1 mod 41
--> kleiner Satz von Fermat:
1^25 mod 41 = 1 mod 41
Forensoftware: Burning Board, entwickelt von WoltLab GmbH