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

4

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.

  • 0
    Dude, your like a mathemagician or something. All of you have helped me so very much. Thanks.2012-09-23
3

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

  • 0
    @RagibZaman: good point. I have added some details.2012-09-22
3

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$.