What is $1000 \choose 326$ $\mod{13}$?

Question

$1000=5(13^2)+11(13)+12$

$326=1(13^2)+12(13)+1$

Now, using Lucas theorem we have

$1000 \choose 326$$\equiv$$5 \choose 1$$11 \choose 12$$12 \choose 1$ $\pmod{13}$

Here, we got into the trouble since $11 \choose 12$ is not defined.

So, how do we compute this?

Answer 1

You can fast find n and k in t! = p^n * (p*m + k) using recurrent t! = p^(t div p) * ((t mod p)! mod p ) * (-1)^(t div p)* (t div p)! ( (p-1)! mod p = -1)

if n(1000, 13) > n(326, 13) + n(674, 13) - answer is 0, else answer is k(1000, 13)/(k(326, 13)*k(674, 13))

simple codepad listing in your case answer is 0

Answer 2

The exponent of 13 on the factorisation of $1000!$ is $\lfloor\frac{1000}{13}\rfloor+\lfloor\frac{1000}{13^2}\rfloor$ do the same for $326!$ and $674!$ and you'll find that after dividing the exponent on 13 will be greater than one, so the residue modulo 13 is 0.