Zeige, dass 41|(17^1000)-1 |
13.12.2016, 20:13 | Linsane | Auf diesen Beitrag antworten » | ||
Zeige, dass 41|(17^1000)-1 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 |
||||
13.12.2016, 21:08 | 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 |
||||
13.12.2016, 23:27 | mYthos | Auf diesen Beitrag antworten » | ||
RE: Zeige, dass 41|(17^1000)-1
Deswegen: Wenn 41 | (a - 1), dann hinterlässt a bei Division durch 41 den Rest 1 --------- Alternative zum Beweis (eher intuitiv): |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|