Divisionsrest bei Fakultäten

06.11.2015, 12:17	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?
06.11.2015, 22:12	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?
06.11.2015, 22:32	HAL 9000	Auf diesen Beitrag antworten »
$\begin{align} (p-1)! \equiv -1\bmod p \end{align}$ ist klar (Satz von Wilson). Von da ab kannst du rückrechnen: Division durch $\begin{align} (p-1)\equiv -1\bmod p \end{align}$ ergibt $\begin{align} (p-2)! \equiv 1\bmod p \end{align}$ für $\begin{align} p\geq 2 \end{align}$ . Division durch $\begin{align} (p-2)\equiv -2\bmod p \end{align}$ ergibt $\begin{align} (p-3)! \equiv \frac{1-p}{-2} = \frac{p-1}{2} \bmod p \end{align}$ für $\begin{align} p\geq 3 \end{align}$ . Wenn man weiter zurück rechnen will, geht das nicht ohne Fallunterscheidung bzgl. $\begin{align} p \end{align}$ : 1.Fall: $\begin{align} p=6k+1 \end{align}$ mit dann $\begin{align} (p-2)! \equiv 3k \bmod p \end{align}$ Hier ist dann $\begin{align} (p-4)! \equiv \frac{3k}{-3} = -k \bmod p \end{align}$ . 2.Fall: $\begin{align} p=6k-1 \end{align}$ mit dann $\begin{align} (p-2)! \equiv 3k-1 \bmod p \end{align}$ Hier ist dann $\begin{align} (p-4)! \equiv \frac{3k-1-(6k-1)}{-3} = k \bmod p \end{align}$ . Noch weiter zurück wird's zunehmend ekliger, es "zerfasert" in immer mehr Unterfälle, mit geometrischer Geschwindigkeit...
06.11.2015, 23:53	Hosenschlange	Auf diesen Beitrag antworten »
Gar so einfach ist ja auch langweilig. Trotzdem vielen Dank bis hierher! Ich werde das erstmal sacken lassen und durchrechnen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »