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.

I have an equation in the form of n!/c where c is a constant.

I want to find n!/c mod m but I can't seem to get the right value. I tried multiplying n! manually applying mod m at each step but then it doesn't seem to work when dividing it by c mod m, etc.

Mainly, n!/c doesn't compute directly because n! is so large, but then trying to slice down n! as I calculate it renders it incompatible with my c term. Not sure what to do here.

share|improve this question
    
What do you mean by "renders it incompatible with my c term"? –  Robert Israel Mar 13 '12 at 20:02
    
As in I try to modify the c term to get the entire express to yield the right value but to no avail –  John Smith Mar 13 '12 at 20:12
add comment

1 Answer

up vote 1 down vote accepted

You can only "divide by $c$ mod $m$" if $c$ and $m$ are relatively prime. Is that the case?

It may also help to note that if $m \le n$, $n! \equiv 0 \mod m$.

share|improve this answer
    
For instance let's say I have 10!/4 and I want to find this value mod 17. 10!/4 is 907200, mod 17 = 12. So theoretically I want to be able to handle this calculation without needing to calculate 10! fully first, since in much larger cases, it's not feasible. –  John Smith Mar 13 '12 at 20:16
2  
Ok, 4 and 17 are relatively prime. To calculate $10! \mod 17$, you just perform successive multiplications mod $17$. Of course one of the factors to multiply is $4$, so you can just leave that one out rather than dividing by $4$ at the end. Thus: $2 \times 3 = 6$, $6 \times 5 = 30 \equiv 13 \mod 17$, $13 \times 6 = 78 \equiv 10 \mod 17, \ \ldots$. –  Robert Israel Mar 13 '12 at 20:28
add comment

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.