Divisionsrest bei Fakultäten

Neue Frage »

Hosenschlange Auf diesen Beitrag antworten »
Divisionsrest bei Fakultäten
Ich habe folgende Aufgabenstellung:
Gegeben seien zwei Zahlen, n und p, wobei p eine Primzahl ist und n < p gilt. Es soll n! mod p bestimmt werden.

Meine Erkenntnisse:
1. Wenn n = p - 1, dann ist auch der Divisionsrest = p - 1.
2. Wenn n = p - 2, dann ist der Divisionsrest = 1.
3. Wenn n = p - 3, dann ist der Divisionsrest = (p-1)/2.
4. Wenn n = 0 oder 1, dann ist der Divisionsrest zwangsläufig = 1.

Problematisch wird's, wenn n um einiges größer wird. Gibt es eine Möglichkeit, den Divisionsrest zu bestimmen, ohne n! explizit berechnen zu müssen?
Hosenschlange Auf diesen Beitrag antworten »

Zu n = p - 3 lässt sich auch das Modulare Inverse [wegen (p - 2) * x = 1 (mod p)] heranziehen. Ich habe allerdings noch kein Gegenbeispiel gefunden, dass das Ergebnis ungleich (p - 1) / 2 ist.

In meiner Frage geht es mir speziell um die Fortführung der Reihe; also ob es für n = p - 4, p - 5, p - 6 eine ebenso einfache Fortführung gibt wie für n = p - 1, p - 2 oder p - 3...

Voraussetzung ist, dass p natürlich größer/gleich des größten Substrahents ist (wenn n = p - 1, ..., p - 9 ist, dann muss p zwangsläufig größer/gleich 11 sein).

Hat evtl jemand eine Idee?
 
 
HAL 9000 Auf diesen Beitrag antworten »

ist klar (Satz von Wilson).

Von da ab kannst du rückrechnen: Division durch ergibt

für .

Division durch ergibt

für .

Wenn man weiter zurück rechnen will, geht das nicht ohne Fallunterscheidung bzgl. :


1.Fall: mit dann

Hier ist dann .


2.Fall: mit dann

Hier ist dann .


Noch weiter zurück wird's zunehmend ekliger, es "zerfasert" in immer mehr Unterfälle, mit geometrischer Geschwindigkeit...
Hosenschlange Auf diesen Beitrag antworten »

Gar so einfach ist ja auch langweilig. Trotzdem vielen Dank bis hierher! Freude

Ich werde das erstmal sacken lassen und durchrechnen Wink
Neue Frage »
Antworten »



Verwandte Themen

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