87^17 im Z15 berechnen

Neue Frage »

aipubgqerg Auf diesen Beitrag antworten »
87^17 im Z15 berechnen
Hallo,

ich weiß nicht wie ich 87^17 im Ring Z15 lösen soll. Das ganze ohne Taschenrechner. Eine Schritt für Schritt anleitung wäre nicht schlecht. Dass man Fermat nehmen muss ist mir klar, allerdings komme ich damit überhaupt nicht klar.

Danke im Voraus für die Hilfe
lgrizu Auf diesen Beitrag antworten »
RE: 87^17 im Z15 berechnen
Zuerst einmal wähle den betragskleinsten Repräsentanten der Restklasse modulo 15, in der auch 87 liegt, welcher ist das?
aipubgqerg Auf diesen Beitrag antworten »

wäre das -3?
lgrizu Auf diesen Beitrag antworten »

Jap.

Wir können erst mal Fermat anwenden, der sagt uns, dass gilt .

Welches ist unser p ?
aipubgqerg Auf diesen Beitrag antworten »

Wäre unser p jetzt 3? Oder wie komm ich auf das p?
lgrizu Auf diesen Beitrag antworten »

Man müsste zuerst einmal 15 in Primzahlen zerlegen, denn 15 ist keine Primzahl, aber 15=3*5

Also können wir zuerst modulo 3 rechnen und nutzen, dass ist.
 
 
aipubgqerg Auf diesen Beitrag antworten »

Also dass (-3)^3 = (-3) mod 3 ist kommt von Fermat. nur warum ist das (-3) mod (3*5)?
lgrizu Auf diesen Beitrag antworten »

Das kann man aus Fermat und der Eulerschen Phi-Funktion herleiten.
diesdas Auf diesen Beitrag antworten »

Achso.
aipubgqerg Auf diesen Beitrag antworten »

und wie mach ich dann weiter?
lgrizu Auf diesen Beitrag antworten »

Entweder benutzen wir, dass gilt:



oder

Wir zerlegen in

Edit: Sorry, ich hab mich vertan, es gilt natürlich
Neue Frage »
Antworten »



Verwandte Themen

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