Modulus simplification

Trying to get the modulus of the five numbers immediately before a prime, added together in there factorial form; I'll call this operation $S(p)$. For example,

$$S(p) = ((p-1)! + (p-2)! + (p-3)! + (p-4)! + (p-5)!) \bmod p$$

$$S(5) = (4!+3!+2!+1!+0!) \bmod 5$$

$$S(5) = 4$$

However, I have to do the operation many hundreds of times for my question, and calculating the factorial of all the numbers from $5$ to $10^8$ is impossible within my one minute time frame.

I am looking for a way to simplify the modulus operation and the work itself. Found out that by modulus Congruency, and only having to calculate primes, I can simplify the expression a little.

$$S(p) = ((p-1) + (1) + (p/2) + (p-4)! + (p-5)!) \bmod p;$$

$$S(p) = ((p/2) + (p-4)! + (p-5)!) \bmod p;$$

I need to simplify $(p-4)! + (p-5)!$, which has led me to this costly operation.

i is the integer solution to $(p-4)! \bmod p = i(p - 3) \bmod p = \frac{p}{2}$; using $i$, $(p-5)!$ can be found.

$k$ is the integer solution to $k(p - 4) \bmod p = i$;

At the moment I have to iterate over all the possible solutions from $1$ to $\frac{i}{k}$. (My answers will only be positive integers I will note)

Besides my poor knowledge of mathematical notation and the modulus operator, I was wondering if it is possible to simplify this operation from the costly depths of blind iteration. Thanks.

-

You could use Wilson's theorem, $(p-1)!=-1 \pmod p$ when (and only when) $p$ is prime. This makes your expression $-1+\frac {-1}{p-2} + \ldots \pmod p$ so you just need four inverses $\pmod p$

Multiplicative inverses $\pmod p$ are numbers that multiply to $1.$ When $p$ is prime, all numbers not divisible by $p$ have them. For example modulo $11$, the inverse pairs are $3$ and $4, 2$ and $6, 5$ and $9, 7$ and $8.\ \ 1$ and $10$ are their own inverses. You can multiply each pair and see that it comes out $1\pmod{11}.$

To find the Modular multiplicative inverse you use the Extended Euclidean algorithm

-
(+1) While this is a good answer, I fear the OP will not understand it unless it is fleshed out a little bit more. His question gave me the impression he is very unfamiliar with modulo arithmetic and may not understand the notation of $\frac{-1}{p-2} \mod p$ or how to compute inverses in mod p. –  Ragib Zaman Sep 22 '12 at 14:34
@RagibZaman: good point. I have added some details. –  Ross Millikan Sep 22 '12 at 14:52

This isn't a complete answer, but it may be helpful. Note the following:

$(p-1)! + (p-2)! + (p-3)! + (p-4)! + (p-5)!$

$= (p-5)![(p-1)(p-2)(p-3)(p-4) + (p-2)(p-3)(p-4) + (p-3)(p-4) + (p-4) + 1]$

$\equiv (p-5)![(-1)(-2)(-3)(-4) + (-2)(-3)(-4) + (-3)(-4) + (-4) + 1]\ \textrm{mod}\ p$

$\equiv 9(p-5)!\ \textrm{mod}\ p.$

So all you need to do now is figure out $(p - 5)!\ \textrm{mod}\ p$. You could do this as Ross' answer suggests, that is, find $a$ such that $a[-1(p-1)(p-2)(p-3)(p-4)] \equiv 1\ \textrm{mod}\ p$, then $(p-5)! \equiv a\ \textrm{mod}\ p$.

-

We produce a concrete and easy to calculate "formula" that is useful if we need to compute the answer for a number of values of $p$.

Let $x=(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!$. Then, as shown by Michael Albanese, we have $$x\equiv 9(p-5)!\pmod{p}.$$ But $p-3\equiv -3\pmod{p}$, and therefore $$x\equiv (-3)(p-5)!(p-3)\pmod{p}.$$ Multiply both sides by $(p-1)(p-2)(p-4)$, modulo $p$. Since $(p-4)(p-2)(p-1)\equiv -8\pmod{p}$, we obtain $$-8x\equiv (-3)(p-1)! \pmod{p}.$$ By Wilson's Theorem, $(p-1)!\equiv -1\pmod{p}$. Thus we obtain the Master Congruence $$8x\equiv -3\pmod{p}.\tag{1}$$

It remains to solve Congruence $(1)$. There are four cases: (a) $p\equiv 1\pmod{8}$; (b) $p\equiv 3\pmod{8}$; (c) $p\equiv 5\pmod{8}$; and (d) $p\equiv 7\pmod{8}$.

The answers are not hard to obtain. As an example, for (a) we want an $x$ such that when we multiply $x$ by $8$ and add $-3$, we get something divisible by $p$. Then $x=(3p-3)/8$ works. Since $p\equiv 1\pmod{8}$, the number $3p-3$ is divisible by $8$. Multiply it by $3$. We get $3p-3$, which, as desired, is congruent to $-3$ modulo $p$. The other cases are dealt with similarly. We end up with the following result.

(a) If $p$ is congruent to $1$ modulo $8$, or equivalently if $p$ is of the shape $8k+1$, then the desired remainder is $\dfrac{3p-3}{8}$.

(b) If $p$ is of the shape $8k+3$, then the desired remainder is $\dfrac{p-3}{8}$.

(c) If $p$ is of the shape $8k+5$, then the desired remainder is $\dfrac{7p-3}{8}$.

(d) If $p$ is of the shape $8k+7$, then the desired remainder is $\dfrac{5p-3}{8}$.

For example, let $p=47$. Then we are in case (d), and the result is $\dfrac{(5)(47)-3}{8}$, which is $29$.

Remark: One can use tricks to transform the above "cases" formula into a single formula that uses only arithmetical operations. But in almost all situations that is not worth doing.

-
Dude, your like a mathemagician or something. All of you have helped me so very much. Thanks. –  Dan Sep 23 '12 at 0:27