Forum:  Zahlentheorie
Thema: Der kleine Fermat
Themen-Übersicht
Cinimod
Aktiv
Dabei seit: 06.07.2002
Mitteilungen: 340
Aus:
Themenstart: 2007-04-17 14:07

fed-Code einblenden

ich habe eine Frage zur Anwendung des kleinen Satzes von Fermat:

Berechnen möchte ich den Rest von 7^999 bei Division durch 15.

Nach Fermat gilt: 7^14 == 1 mod 15

a^(14*k) = (a^14)^k == 1^k = 1 mod 15

Somit ist: (14*70 = 980)

7^999 = 7^(14*70)*7^19 == 7^19 mod 15

Jetzt stellt sich für mich die Frage, wie ich denn 7^19 modulo 15
ausrechne?

Vielen Dank für Hilfe im voraus!
fed-Code einblenden


owk
Senior
Dabei seit: 10.01.2007
Mitteilungen: 6957
Aus:
Beitrag No.1, eingetragen 2007-04-17 14:10

fed-Code einblenden
Hallo. 7^14==4 mod 15, aber 7^8==1 mod 15. Stichwort \phi(15)=8, Satz von Euler\-Fermat. owk
fed-Code einblenden


Cinimod
Aktiv
Dabei seit: 06.07.2002
Mitteilungen: 340
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2007-04-17 14:41

Euler Fermat darf ich leider nicht benutzen, da wir ihn nicht bewiesen haben...mit Fermat alleine geht´s also nicht?


owk
Senior
Dabei seit: 10.01.2007
Mitteilungen: 6957
Aus:
Beitrag No.3, eingetragen 2007-04-17 14:46

Fermat und chinesischer Restsatz geht auch:
fed-Code einblenden
owk


Cinimod
Aktiv
Dabei seit: 06.07.2002
Mitteilungen: 340
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2007-04-17 18:11

fed-Code einblenden
mir ist ein Fehler passiert: (14*70 = 980) -> 14*71 = 994 geht natürlich besser.

damit ergibt sich:

7^999 = 7^(14*71)*7^5 == 7^5 mod 15

Jetzt berechne ich ganz einfach:

7^5 = 7 mod 15

Da muss aber 13 rauskommen?

Vielen Dank für Hilfe im voraus!
fed-Code einblenden


Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1361
Aus: Koblenz (früher: Berlin)
Beitrag No.5, eingetragen 2007-04-17 18:47

Hallo,

Es geht auch über einen anderen Weg:

fed-Code einblenden

Kay


Cinimod
Aktiv
Dabei seit: 06.07.2002
Mitteilungen: 340
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2007-04-17 18:54

ja, Danke...nur wo ist mein Fehler wenn ich es stur nach Fermat machen will?


Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1361
Aus: Koblenz (früher: Berlin)
Beitrag No.7, eingetragen 2007-04-17 19:29

Du kannst den kleinen Fermat gar nicht anwenden, da 15 keine Primzahl ist.

Also bleiben die angesprochenen Wege: Eulersche Phi-Funktion, Chinesischer Restsatz etc.

Kay




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=77981=90
Druckdatum: 2020-08-10 12:59