Autor |
Der kleine Fermat |
|
Cinimod
Ehemals Aktiv  Dabei seit: 06.07.2002 Mitteilungen: 340
 |
 
Hallo, 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!
|
Notiz Profil
Quote
Link |
owk
Senior  Dabei seit: 10.01.2007 Mitteilungen: 6957
 |     Beitrag No.1, eingetragen 2007-04-17
|
Notiz Profil
Quote
Link |
Cinimod
Ehemals Aktiv  Dabei seit: 06.07.2002 Mitteilungen: 340
 |     Beitrag No.2, vom Themenstarter, eingetragen 2007-04-17
|
Euler Fermat darf ich leider nicht benutzen, da wir ihn nicht bewiesen haben...mit Fermat alleine geht´s also nicht?
|
Notiz Profil
Quote
Link |
owk
Senior  Dabei seit: 10.01.2007 Mitteilungen: 6957
 |     Beitrag No.3, eingetragen 2007-04-17
|
Fermat und chinesischer Restsatz geht auch:
 
\ 7^4 == 1 mod 5 7^2 == 1 mod 3, also 7^4 == 1 mod 15.
owk
|
Notiz Profil
Quote
Link |
Cinimod
Ehemals Aktiv  Dabei seit: 06.07.2002 Mitteilungen: 340
 |     Beitrag No.4, vom Themenstarter, eingetragen 2007-04-17
|
 
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!
|
Notiz Profil
Quote
Link |
Kay_S
Senior  Dabei seit: 06.03.2007 Mitteilungen: 1366
Herkunft: Koblenz (früher: Berlin)
 |     Beitrag No.5, eingetragen 2007-04-17
|
Hallo,
Es geht auch über einen anderen Weg:
 
7^2 = 49 = 4 (mod 15) => 7^4 = 4^2 = 1 (mod 15) => 7^996 = (7^4)^249 = 1^249 = 1 (mod 15) => 7^999 = 7^3 = 7^2 * 7 = 4 * 7 = 28 = 13 (mod 15)
Kay
|
Notiz Profil
Quote
Link |
Cinimod
Ehemals Aktiv  Dabei seit: 06.07.2002 Mitteilungen: 340
 |     Beitrag No.6, vom Themenstarter, eingetragen 2007-04-17
|
ja, Danke...nur wo ist mein Fehler wenn ich es stur nach Fermat machen will?
|
Notiz Profil
Quote
Link |
Kay_S
Senior  Dabei seit: 06.03.2007 Mitteilungen: 1366
Herkunft: Koblenz (früher: Berlin)
 |     Beitrag No.7, eingetragen 2007-04-17
|
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
|
Notiz Profil
Quote
Link |