-1
$\begingroup$

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.

  • 0
    As in I try to modify the c term to get the entire express to yield the right value but to no avail2012-03-13

1 Answers 1

1

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

  • 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$.2012-03-13