Berechnung mithilfe Kl. Satz v. Fermat |
14.11.2012, 00:25 | Naryxus | Auf diesen Beitrag antworten » | ||||||||
Berechnung mithilfe Kl. Satz v. Fermat ich soll folgenden Term ohne elektronische Hilfsmittel berechnen: Es wäre lieb, wenn jemand mal über meine Rechnung schauen könnte (ich habe den kleinen Satz von Fermat nämlich noch nicht so ganz verinnerlicht...): Aus dem kleinen Satz von Fermat folgt jetzt für , da 2 eine Primzahl ist: Das heißt liegt in der gleichen Restklasse wie . Da 5 in der Restklasse liegt, liegt auch in der Restklasse . Demnach kann ich durch ersetzen. Daraus ergibt sich: Auch hier kann man gleichermaßen den kleinen Satz von Fermat anwenden: 218 liegt in der Restklasse . Also liegt ebenfalls darin. Also kann ich durch ersetzen und erhalte damit: Wenn da was nicht stimmt, könntet ihr mir bitte helfen? Liebe Grüße, Naryxus |
||||||||||
14.11.2012, 00:36 | lgrizu | Auf diesen Beitrag antworten » | ||||||||
RE: Berechnung mithilfe Kl. Satz v. Fermat Aber Also ziemlich daneben deine Ausführung. Du kannst ausnutzen, dass 223 eine Primzahl ist, also mit Sicherheit teilerfremd zu jeder Potenz von 5 und dann den kleinen Fermat anwenden.... |
||||||||||
14.11.2012, 08:23 | Mystic | Auf diesen Beitrag antworten » | ||||||||
RE: Berechnung mithilfe Kl. Satz v. Fermat
Naja, man sollte ja auch "ohne elektronische Hilfsmittel" auskommen, also ganz so einfach wird es dann doch nicht gehen... Sicher eine Rolle spielt dabei auch, dass ist... |
||||||||||
14.11.2012, 11:53 | Naryxus | Auf diesen Beitrag antworten » | ||||||||
Jetzt bringt ihr mich wieder durcheinander
Jetzt wo du es sagst, fällt es mir auch auf. Ich hätte jetzt einfach umgeformt: Nochmal zum Verständnis: Darf jetzt 5 kein Vielfaches von 223 sein oder 5^222? Wann darf ich denn den kleinen Satz von Fermat anwenden?
Darf ich dann in umwandeln? Wenn ja, wie begründe ich das dann? Und vor allem wie würde mich das denn weiterbringen? Dann habe ich ja weiterhin ziemlich unschöne 5er-Potenzen da stehen und komme immer noch nicht weiter. Irgendwie komme ich mit der modularen Arithmetik und Teilbarkeit nicht zurecht... |
||||||||||
14.11.2012, 12:14 | lgrizu | Auf diesen Beitrag antworten » | ||||||||
Das ist auch richtig, fernerhin ist nun nach Fermat
Nein, aber in
Einfach weil gilt: , also beide in der selben Restklasse modulo 223 liegen, sprich, den selben Rest bei Division durch 223 hinterlassen.
Das bringt dich dahingehend weiter, dass du mit betragskleineren Zahlen rechnen kannst. |
||||||||||
14.11.2012, 22:44 | Naryxus | Auf diesen Beitrag antworten » | ||||||||
Okay. Also nur nochmal zum Verständnis: Bei dem kleinen Satz von Fermat gilt ja für eine ganze Zahl a und eine Primzahl p, die a nicht teilt. Das heißt auf die Aufgabe bezogen, dass 5 nicht durch 223 teilbar sein darf oder 5^223? Weiterhin habe ich mich dann mal nach eurer Anleitung an der Aufgabe versucht: Soweit erstmal. Jetzt habe ich mir gedacht, dass 666888 bestimmt durch 222 teilbar ist, damit ich letztendlich wieder auf eine Anwendung des kleinen Fermats komme. Allerdings frage ich mich, ob mir diese Rechnung dann noch als Berechnung ohne elektronische Hilfsmittel abgenommen wird. Was meint ihr? Gäbe es einen anderen Lösungsweg? Mit meiner Idee komme ich dann zu folgendem: Bin ich damit endlich am Ziel? |
||||||||||
Anzeige | ||||||||||
|
||||||||||
15.11.2012, 08:23 | Mystic | Auf diesen Beitrag antworten » | ||||||||
Das Ergebnis stimmt zwar, aber du rechnest das etwas zu kompliziert... Tatsächlich ist Und ja, die Beziehung scheint wider Erwarten doch keine Rolle zu spielen... Edit: Der aufwändigste Teil der ganzen Rechnung scheint also die Überprüfung von 223 auf Primalität zu sein... |
||||||||||
16.11.2012, 19:06 | Perky | Auf diesen Beitrag antworten » | ||||||||
Wenn ich das richtig sehe sitzen wir an den gleichen Hausaufgaben ^^ Ich verstehe nur leider noch nicht, wieso bei die Klammern plötzlich wegfallen. Letztes Jahr in der Klausur mussten wir auch nicht nachweisen, dass 223 eine Primzahl ist. Der Hinweis, dass man den kleinen Satz von Fermat verwenden soll reicht eigentlich dafür ^^ |
||||||||||
16.11.2012, 19:27 | lgrizu | Auf diesen Beitrag antworten » | ||||||||
Welche Klammern? |
||||||||||
16.11.2012, 19:44 | tcp | Auf diesen Beitrag antworten » | ||||||||
Sitze wohl auch an dem gleichen Blatt :-) Wir brauchen lt. HiWi nicht nachweisen das 223 eine Primzahl ist ;-) |
||||||||||
16.11.2012, 19:57 | Perky | Auf diesen Beitrag antworten » | ||||||||
Naja, der ganze Teil nach 4* verschwindet ja. Aber ich verstehe nicht, wieso. |
||||||||||
16.11.2012, 20:00 | lgrizu | Auf diesen Beitrag antworten » | ||||||||
Weil (für ggt(a,223)=1) ist, und |
||||||||||
16.11.2012, 20:07 | Perky | Auf diesen Beitrag antworten » | ||||||||
Kopf -> Tisch Danke!!! Der Tag heute war wohl zu lang -.- |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|