1
$\begingroup$

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.

3 Answers 3