Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 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

share|improve this answer
    
(+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$.

share|improve this answer

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.