Berechnung mithilfe Kl. Satz v. Fermat

Neue Frage »

Naryxus Auf diesen Beitrag antworten »
Berechnung mithilfe Kl. Satz v. Fermat
Huhu,

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
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....
Mystic Auf diesen Beitrag antworten »
RE: Berechnung mithilfe Kl. Satz v. Fermat
Zitat:
Original von lgrizu
Du kannst ausnutzen, dass 223 eine Primzahl ist, also mit Sicherheit teilerfremd zu jeder Potenz von 5 und dann den kleinen Fermat anwenden....

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... Augenzwinkern
Naryxus Auf diesen Beitrag antworten »

Jetzt bringt ihr mich wieder durcheinander Big Laugh

Zitat:
Original von Mystic
Naja, man sollte ja auch "ohne elektronische Hilfsmittel" auskommen,


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?


Zitat:
Original von Mystic
Sicher eine Rolle spielt dabei auch, dass ist...


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... unglücklich
lgrizu Auf diesen Beitrag antworten »

Zitat:
Original von Naryxus

Jetzt wo du es sagst, fällt es mir auch auf. Ich hätte jetzt einfach umgeformt:


Das ist auch richtig, fernerhin ist nun nach Fermat




Zitat:
Original von Naryxus
Darf ich dann in umwandeln?


Nein, aber in Augenzwinkern

Zitat:
Original von Naryxus
Wenn ja, wie begründe ich das dann?


Einfach weil gilt: , also beide in der selben Restklasse modulo 223 liegen, sprich, den selben Rest bei Division durch 223 hinterlassen.


Zitat:
Original von Naryxus
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.


Das bringt dich dahingehend weiter, dass du mit betragskleineren Zahlen rechnen kannst.
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?
 
 
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... Augenzwinkern

Edit: Der aufwändigste Teil der ganzen Rechnung scheint also die Überprüfung von 223 auf Primalität zu sein...
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 ^^
lgrizu Auf diesen Beitrag antworten »

Welche Klammern? verwirrt
tcp Auf diesen Beitrag antworten »

Sitze wohl auch an dem gleichen Blatt :-) Wir brauchen lt. HiWi nicht nachweisen das 223 eine Primzahl ist ;-)
Perky Auf diesen Beitrag antworten »

Naja, der ganze Teil nach 4* verschwindet ja. Aber ich verstehe nicht, wieso.
lgrizu Auf diesen Beitrag antworten »

Weil (für ggt(a,223)=1) ist, und
Perky Auf diesen Beitrag antworten »

Kopf -> Tisch

Danke!!! Der Tag heute war wohl zu lang -.-
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »