Informatiker Board | Informatik in der Schule | Zeige, dass 41|(17^1000)-1

Informatiker Board » Themengebiete » Informatik in der Schule » Zeige, dass 41|(17^1000)-1 » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

Linsane

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