Zeige, dass 41|(17^1000)-1

Neue Frage »

Linsane Auf diesen Beitrag antworten »
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
RavenOnJ Auf diesen Beitrag antworten »
RE: Zeige, dass 41|(17^1000)-1
Erstmal gilt wegen dem kleinen Fermat, dass , wobei die Eulersche -Funktion ist. Da 41 eine Primzahl ist, gilt , also

Da außerdem , gilt wegen der Rechengesetze der modularen Arithmetik
.
Also
mYthos Auf diesen Beitrag antworten »
RE: Zeige, dass 41|(17^1000)-1
Zitat:
Original von Linsane
...
Warum darf man diese Umformung ausführen?
...

Deswegen: Wenn 41 | (a - 1), dann hinterlässt a bei Division durch 41 den Rest 1
---------
Alternative zum Beweis (eher intuitiv):

Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »